1437: 环形畜棚1

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

题目描述

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

       约翰想让第i个房间有ri头奶牛,于是他决定打开某个房间的外门,让所有的奶牛都进入这个房间,然后每个奶牛都要沿着顺时针方向走到自己最终要去的地方。很明显,不同的外门打开对于最终所有奶牛要行走的总路程是不一样的。现在,请你来计算所有奶牛最小的总路程。每头奶牛的路程等于他经过的内门数量。

输入格式

     输入文件第一行是一个正整数n,表示有n个房间,接下来n行,表示每个房间需要有的奶牛数量,即ri,按照顺时针方向。

输出格式

输出文件只有一行一个整数,表示所有奶牛最少的总路程。

输入样例 复制

5
4
7
8
6
4

输出样例 复制

48

数据范围与提示

【输入输出样例1说明】

所有奶牛从要有7头奶牛的房间进入,这样的总路程最短,只要48

【数据说明】

3<=n<=1000,1<=ri<=100