1439: 环形畜棚2

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:38 通过:16

题目描述

农夫约翰对现代建筑学非常感兴趣,于是他把他的畜棚连起来建成了一个完美的圆形,每个畜棚代表一个房间,总共有n个房间(顺时针编号从1n)。每个房间都有一扇可以通向相邻两个房间的门(内门),同时,每个房间也各有一扇通向外面的门(外门)。

约翰想让每个房间有且仅有一头奶牛,但是初始的时候,每个房间里面有ci头奶牛,数据保证所有ci加起来一定是n

接下来,每头奶牛将沿着顺时针方向行走,直到每个房间都恰好只有一头奶牛,每头奶牛行走消耗的能量就是通过的内门数量的平方(即如果某头奶牛总共通过了d扇内门,那么这头奶牛消耗的能量就是d*d)。

现在请你计算所有的这些奶牛所需要消耗的能量总和的最小值。

输入格式

       输入文件第一行是一个正整数n,表示有n个房间,接下来n行,每行一个整数ci表示初始的时候每个房间的奶牛数量,顺时针输入,保证所有ci的总和一定是n

输出格式

        输出文件只有一行一个整数,表示所有奶牛所需要消耗的能量总和的最小值。

输入样例 复制

10
1
0
0
2
0
0
1
2
2
2

输出样例 复制

33

数据范围与提示

【输入输出样例1说明】

最小的能量消耗总和是33

【数据说明】

3<=n<=1000