测试数据来自 system/2160

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

---

【题目描述】

　　暑作为当代建筑的爱好者，FJ 建造了一个圆形新谷仓，谷仓内部 \(n\) 个房间排成环形（），按顺时针顺序编号为 \(1..n\)，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

　　现在 FJ 有 \(n\) 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第 \(i\) 个房间里有 \(c_i\) 头奶牛。保证 \(∑c_i=n\)。

　　FJ 决定采用这样的方法来解决这个问题：让某些奶牛顺时针穿过某些房间到达指定的位置。如果一头奶牛穿过了 \(d\) 扇门，他消耗的能量为 \(d^2\)。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。

【输入格式】

　　第一行一个整数 \(n\)，接下来 \(n\) 行，第 \(i\) 行一个整数 \(c_i\)。

【输出格式】

　　输出所有奶牛最小消耗能量和。

【输入输出样例】

　Input

10
1
0
0
2
0
0
1
2
2
2

　Output

33

【数据限制】

　　对于 \(20\%\) 的数据，\(3≤n≤100,000\)

【来源】

　　Mr.he