4412 - [Usaco2016 Feb]Circular Barn

有一个N个点的环，相邻两个点距离是1。点顺时针标号为1..N。 每一个点有ci头牛，保证∑ci=N。 每头牛都可以顺时针走。设一头牛走了d个单位停下了，将耗费d^2的能量。 请设计一种牛的走法，使得每一个点上都正好有一头牛，且最小化耗费的能量。

Input

第一行一个数N。N <= 100000 接下来N行，每行一个数ci。

Output

输出一个数表示耗费能量的最小值

Examples

Input

10
1
0
0
2
0
0
1
2
2
2

Output

33
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题