Круглий амбар (Золото)

Фермер Джон, захоплений сучасною архітектурою, побудував новий амбар у формі кола. Всередині амбару розташоване кільце з $n$ кімнат, пронумерованих за годинниковою стрілкою від $1$ до $n$ по периметру. Кожна кімната має двері, що ведуть у дві сусідні кімнати, а також двері, що ведуть назовні.

У фермера є рівно $n$ корів, і він хоче розмістити по одній корові в кожній кімнаті. Проте корови вишикувалися не так, як потрібно, і можливо, кілька з них зібралися біля однієї зовнішньої двері. Зокрема, перед дверима з номером $i$ стоїть $c_i$ корів. Звісно, виконується рівність $\sum c_i=n$.

Щоб корови зайняли свої місця, фермер Джон планує застосувати такий підхід: кожна корова входить у двері, перед якими вона стоїть, і рухається за годинниковою стрілкою до своєї кімнати. Припускаючи, що проходження корови через $d$ дверей забирає у неї $d^2$ енергії, визначте мінімальну кількість енергії, необхідну для розміщення корів по одній у кожну кімнату.

Вхідні дані

Перший рядок містить число $n(3\le n\le 10^6)$. Наступні $n$ рядків містять значення $c_1,...,c_n$.

Вихідні дані

Виведіть мінімальну кількість енергії, витрачену всіма коровами.

Приклади