时间限制：1秒　　内存限制：256M

---

【题目描述】

　　X国的军营是一个圆形的建筑，内部的 \(N\) 个房间排成环形，按顺时针顺序编号为 \(1..N\)，每个房间都有通往与其相邻的左右房间的通道。其中第 \(i\) 个房间可以供 \(r_i\) 个士兵休息，军营的士兵总数刚好为 \(∑r_i\)。

　　现在需要打开三扇向外的门，外边的士兵可以随意选择其中的一个进入到建筑内。进入建筑内的士兵可以沿顺时针移动，每穿过一个房间之间的通道，耗费体力为 1。

　　现在需要你来确定，这三扇门开在哪些房间上，才能让所有士兵找到自己的房间耗费的体力和最小。

　　注意，不计算士兵在建筑外的移动而耗费的体力。

【输入格式】

　　第一行两个整数 \(N\)，接下来 \(N\) 行，第 \(i\) 行一个整数 \(r_i\)。

【输出格式】

　　输出所有士兵耗费体力的最小值。

【输入输出样例】

　Input

8
3
4
6
1
2
1
3
5

　Output

17

【样例说明】

　　如下图，分别在 1, 3, 7 号房间打开朝外的门：安排 7 名士兵从 1 号房间的门进入，有 3 名士兵直接住 1 号房间，有 4 名士兵前往 2 号房间，则耗费体力为 4；安排 10 名士兵从 3 号房间的门进入，有 6 名士兵直接住 3 号房间，有 1 名士兵前往 4 号房间，2 名士兵前往 5 号房间，1 名士兵前往 6 号房间，则耗费体力为 8；安排 8 名士兵从 7 号房间的门进入，有 3 名士兵直接住 7 号房间，有 5 名士兵前往 8 号房间，则耗费体力为 5。所以总体里为 4 + 8 +5 = 17。

【数据限制】

　　\(100\%\) 的数据满足：\(1 ≤ N ≤ 1000\)，\(1≤r_i≤1,000,000\)。

【来源】

　　Mr.he