6532 - 糖果传递

有n个小朋友坐成一圈,每人有ai个糖果,每人只能给他左右两边紧邻的人传递糖果,每人每次传递一个糖果代价为1,求使所有人获得均等糖果的最小代价。

输入

输入第一行一个整数n,表示小朋友个数。

接下来n行,每行一个整数ai。

输出

输出使所有人获得均等糖果的最小代价。

样例

输入

4
1
2
5
4

输出

4

来源

一本通

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题