Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из n комнат, пронумерованных по часовой стрелке 1 .. n по периметру. Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.
У ФД есть ровно n коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, c[i]
коров стоит перед дверью с номером i. Разумеется, ∑ c[i]
= n.
Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через d дверей отнимает у неё d^2
энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.
Первая строка содержит n (3 ≤ n ≤ 10^5
). Оставшиеся n строк содержат c[1]
... c[n]
.
Выведите минимальное количество энергии, потреблённое всеми коровами.