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

ФД хочет разместить ровно ri коров а каждой комнате i. Чтобы загонять коров в амбар, он планирует открывать внешнюю дверь в одну из комнат, позволяя всем коровам зайти через эту дверь. Каждая из коров затем идёт по часовой стрелке через все комнаты пока не добредёт до своей. ФД хочет открыть такую внешнюю дверь, чтобы все коровы вместе прошли минимальное суммарное расстояние. Определите это минимальное суммарное расстояние, если ФД выберет дверь для открывания оптимальным образом. Расстояние, которое проходит одна корова, равно количеству внутренних дверей, через которые она прошла.

Пример входа

Первая строка содержит n (3 ≤ n ≤ 1000). Оставшиеся n строк содержат r1, ..., rn (1 ≤ ri ≤ 100).

Пример выхода

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

Пример

В этом примере лучшее решение – позволить коровам войти через дверь комнаты, в которой должно разместиться 7 коров.