JOI君和他的妹妹们一起吃点心。

JOI君正在准备和他的妹妹JOI子和JOI美一起吃点心。今天的点心是他们三个人都喜欢的香糕。

香糕是一种像图中所示的圆柱形甜点。为了分给三个人吃，JOI君需要用刀在半径方向上切三次，将其切成三个部分。然而，这个香糕很硬，就像真木头一样，所以切它并不容易。因此，在香糕上预先切了N个切口，JOI君只能在这些切口处切割。当切口编号从1到N按顺时针方向排列时，对于1 ≤ i ≤ N-1，第i个切口和第i+1个切口之间的部分大小为Ai。最后一个切口和第一个切口之间的部分大小为AN。

图1：香糕的一个例子，N = 6，A1 = 1，A2 = 5，A3 = 4，A4 = 5，A5 = 2，A6 = 4

JOI君非常关心他的妹妹们，所以在将香糕切割成三份后，他打算选择最小的一份给自己，将剩下的两份分给他的两个妹妹。然而，JOI君非常喜欢香糕，希望能吃更多。在保证最小切割块的尺寸最大化的情况下，JOI君能吃到的切块的大小是多少呢？

任务

给定切口的个数N和每个部分的大小A1, ..., AN，编写一个程序来计算将香糕切割成三份后，最小切割块的最大尺寸。

---

输入

从标准输入读取以下输入：

• 第一行包含整数N，表示香糕上有N个切口。
• 接下来的N行中，第i行（1 ≤ i ≤ N）包含整数Ai，表示第i个切口和第i+1个切口之间的部分的大小（当i = N时，表示第N个切口和第一个切口之间的部分）

输出

在标准输出中输出一个整数，表示将香糕切割成三份后，最小切割块的最大尺寸。

---

限制

所有输入数据满足以下条件：

• 3 ≤ N ≤ 100,000。
• 1 ≤ Ai ≤ 1,000,000,000（1 ≤ i ≤ N）。

子任务

子任务1 [5 points]

满足N ≤ 100。

子任务2 [15 points]

满足N ≤ 400。

子任务3 [30 points]

满足N ≤ 8,000。

子任务4 [50 points]

无额外限制。

---

示例输入1

6
1
5
4
5
2
4

示例输出1

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

示例输出2

213