[Usaco2016 Feb]Circular Barn

时间限制:10s      空间限制:128MB

题目描述

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


输入格式

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


输出格式

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


样例输入

10
1
0
0
2
0
0
1
2
2
2

样例输出

33

提示

没有写明提示


题目来源

没有写明来源