时间限制：1秒　　内存限制：256M

---

【题目描述】

　　X国的军营是一个圆形的建筑，内部的 \(n\) 个房间排成环形，按顺时针顺序编号为 \(1..n\)，每个房间都有通往与其相邻的左右房间的通道。整个建筑有一扇门通往外面。

　　有 \(n\) 名士兵，先是随意待在一些房间，第 \(i\) 个房间里有 \(r_i\) 人。到晚上每个房间只能有一人，所以到晚上就寝号吹响后，所以人必须通过房间之间的通道尽快回到属于自己的房间。

　　士兵们可以顺时针穿过某些房间和通道到达指定的房间。如果一名士兵通过 \(x\) 个通道，需要消耗 \(x^2\) 体力。那么该怎样指定每个士兵的房间，才能让他们消耗的体力和最小。

【输入格式】

　　第一行一个整数 \(n\)，接下来 \(n\) 行，第 \(i\) 行一个整数 \(r_i\)。保证 \(∑r_i=n\)

【输出格式】

　　输出所有士兵最小消耗体力和。

【输入输出样例】

　Input

10
1
0
0
2
0
0
1
2
2
2

　Output

33

【数据限制】

　　\(100\%\) 的数据满足：\(3≤n≤1000\)。

【来源】

　　Mr.he