Круглий амбар (Бронза)

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

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

Вхідні дані

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

Вихідні дані

Виведіть мінімальну сумарну відстань, яку пройдуть усі корови разом.

Приклади

У цьому прикладі найкраще рішення — дозволити коровам увійти через двері кімнати, в якій має розміститися $7$ корів.