JOI 君正准备和他的妹妹 JOI 子和 JOI 美一起吃点心。今天的点心是三个人都非常喜欢的年轮蛋糕。

年轮蛋糕是如下图所示的圆柱形点心。为了分给三个人，JOI 君必须在半径方向上切 3 刀，将其分成 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, \dots, A_N$。请编写一个程序，计算将年轮蛋糕切成 3 块时，最小一块大小的最大值。

输入格式

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

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

输出格式

将将年轮蛋糕切成 3 块时，最小一块大小的最大值作为整数输出到标准输出。

数据范围

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

• $3 \le N \le 100\,000$
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$)

子任务

• 子任务 1 [5 分]：满足 $N \le 100$。
• 子任务 2 [15 分]：满足 $N \le 400$。
• 子任务 3 [30 分]：满足 $N \le 8\,000$。
• 子任务 4 [50 分]：无附加限制。

样例

样例输入 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