Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из \(n\) комнат, пронумерованных по часовой стрелке \(1 \ldots n\) по периметру (\(3 \leq n \leq 100,000\)). Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.
У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату.
Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).
Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через \(d\) дверей отнимает у неё \(d^2\) энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.
ФОРМАТ ВВОДА (файл cbarn.in):
Первая строка ввода содержит \(n\). Оставшиеся \(n\) строк содержат \(c_1 \ldots c_n\).
ФОРМАТ ВЫВОДА (файл cbarn.out):
Выведите минимальное количество энергии, потреблённое всеми коровами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1
0
0
2
0
0
1
2
2
2
|
33
|