Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из \(n\) комнат, пронумерованных по часовой стрелке \(1 \ldots n\) по периметру (\(3 \leq n \leq 1,000\)). Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.
ФД хочет разместить ровно \(r_i\) а каждой комнате \(i\) (\(1 \leq r_i \leq 100\)). Чтобы загонять коров в амбар он планирует открывать внешнюю дверь в одну из комнат, позволяя всем коровам зайти через эту дверь. Каждая из коров затем идёт по часовой стрелке через все комнаты пока не добредёт до своей. ФД хочет открыть такую внешнюю дверь, чтобы все коровы вместе прошли минимальное суммарное расстояние. Определите это минимальное суммарное расстояние, если ФД выберет дверь для открывания оптимальным образом. Расстояние, которое проходит одна корова, равно количеству внутренних дверей, через которые она прошла.
ФОРМАТ ВВОДА (файл cbarn.in):
Первая строка ввода содержит \(n\). Оставшиеся \(n\) строк содержат \(r_1 \ldots r_n\).
ФОРМАТ ВЫВОДА (файл cbarn.out):
Выведите минимальное суммарное расстояние, которое пройдут все коровы вместе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
7
8
6
4
|
48
|