Круглий амбар (Срібло)

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади