题目描述

作为现代建筑的爱好者，农夫约翰新建了一个完美圆形的牛舍。牛舍内部由n个房间组成环形排列，顺时针编号为1到n（3 ≤ n ≤ 1,000）。每个房间有两扇门分别通向相邻房间，还有一扇门通向牛舍外部。

约翰希望每个房间i最终恰好有ri头牛（1 ≤ ri ≤ 100）。为了让牛群有序进入牛舍，他计划解锁一个房间的外部门，让牛群从该门进入。每头牛将顺时针穿过房间，直到找到合适的安置房间。约翰希望选择一个最佳入口，使得所有牛行走的总距离最小（每头牛行走的距离等于其穿过的内部门数量）。

输入格式

• 第一行：整数n
• 随后n行：每行一个整数，表示r1到rn

输出格式

一个整数，表示牛群需要行走的最小总距离

输入输出样例

输入样例 #1

5
4
7
8
6
4

输出样例 #1

48

样例解释

最优方案是让牛群从需要7头牛的房间（第2号房间）进入。