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

У ФД есть ровно n коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, ci коров стоит перед дверью с номером i. Разумеется, ∑ci = n.

Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через d дверей отнимает у неё d2 энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.

Входные данные

Первая строка содержит n (3 ≤ n ≤ 105). Оставшиеся n строк содержат c1 ... cn.

Выходные данные

Выведите минимальное количество энергии, потреблённое всеми коровами.