题目描述

JOI 君马上要和妹妹 JOI 子和 JOI 美一起吃小吃。今天的小吃是他们三个人都很喜欢的年轮蛋糕。

年轮蛋糕是像下图一样呈圆筒形的蛋糕。为了把蛋糕分给三个人，JOI 君必须沿着半径方向切 $3$ 刀，从而把蛋糕分成三块。然而，由于年轮蛋糕硬得像实木一样，要让刀切进去并不简单。因此，这个年轮蛋糕上事先准备了 $N$ 个切口，而 JOI 君只能在有切口的位置下刀。切口按顺时针顺序编号为 $1$ 到 $N$，对于 $1 \le i \le N-1$，第 $i$ 个切口和第 $i+1$ 个切口之间部分的大小是 $A_i$。第 $N$ 个切口和第 $1$ 个切口之间部分的大小是 $A_N$。

图 1：一个年轮蛋糕的例子，$N=6,A_1=1,A_2=5,A_3=4,A_4=5,A_5=2,A_6=4$

妹控的 JOI 君在把蛋糕切成 $3$ 块之后，自己选走最小的一块吃掉，把剩下两块分给两个妹妹。而另一方面，JOI 君太喜欢年轮蛋糕了，只要能吃到的时候就会想吃很多很多。试求：JOI 君吃掉的蛋糕的大小至多不超过多少。

给出切口个数 $N$ 和表示各部分大小的整数 $A_1,\cdots ,A_N$，请求出把年轮蛋糕切成 $3$ 块之后最小一块大小的最大值。

输入格式

第 $1$ 行有一个整数 $N$，表示年轮蛋糕上有 $N$ 个切口；
接下来有 $N$ 行，第 $i(1 \le i \le N)$ 行有一个整数 $A_i$，表示第 $i$ 个切口和第 $i+1$ 个切口之间部分（当 $i=N$ 时即为第 $N$ 个和第 $1$ 个之间部分）的大小。

输出格式

输出一行，一个整数，表示当把年轮蛋糕切成 $3$ 块之后最小块大小的最大值。

样例 1

输入

6
1
5
4
5
2
4

输出

6

图 2：从第 $1,3,5$ 个切口下刀时是最优解（即图中粗实线位置）。

样例 2

输入

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

输出

213

数据范围与提示

全部的输入数据满足：

• $3 \le N \le 100000$
• $1 \le A_i \le 10^9$

子任务

子任务 1（5 分）
满足 $N \le 100$。

子任务 2（15 分）
满足 $N \le 400$。

子任务 3（30 分）
满足 $N \le 8000$。

子任务 4（50 分）
没有额外限制。