说明

JOI 君正打算和他的妹妹 JOI 子以及 JOI 美一起吃点心。今天的点心是三人最爱的年轮蛋糕。

年轮蛋糕是一种如下图所示的圆柱形点心。为了分给三个人，JOI 君必须沿半径方向切三刀，将其分成三块。但是，这个年轮蛋糕像真正的木材一样坚硬，下刀并不容易。因此，这个年轮蛋糕上预先有 $N$ 个切口，JOI 君只能在有切口的位置切割。给切口按顺时针方向从 $1$ 到 $N$ 编号，对于 $1 \le i \le N-1$，第 $i$ 个切口与第 $i+1$ 个切口之间的部分大小为 $A_i$。另外，第 $N$ 个切口与第 $1$ 个切口之间的部分大小为 $A_N$。

:::align{center}

图 1: 年轮蛋糕示例 $N = 6$, $A_1 = 1$, $A_2 = 5$, $A_3 = 4$, $A_4 = 5$, $A_5 = 2$, $A_6 = 4$ :::

体贴妹妹的 JOI 君决定，在将年轮蛋糕切成三块之后，自己选择最小的一块，把剩下的两块分给两个妹妹。另一方面，JOI 君非常喜欢年轮蛋糕，所以他想尽可能多吃一点。当以使得最小的一块尽可能大的方式切割时，JOI 君将吃到的那块蛋糕的大小是多少呢？

任务

给定切口的个数 $N$ 以及表示各部分大小的整数 $A_1, \dots, A_N$。编写程序，输出当年轮蛋糕被切成三块时，最小那块大小的最大值。

输入格式

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

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

输出格式

向标准输出输出一行，包含一个整数，表示当年轮蛋糕被切成三块时，最小那块大小的最大值。

6
1
5
4
5
2
4

6

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

提示

样例解释

:::align{center}

图 2: 在第 1、第 3 和第 5 个切口处切割是最优的。 :::

数据范围

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

• $3 \le N \le 100000$
• $1 \le A_i \le 1000000000$ ($1 \le i \le N$)

子任务

子任务 1 [5 分]

满足 $N \le 100$。

子任务 2 [15 分]

满足 $N \le 400$。

子任务 3 [30 分]

满足 $N \le 8000$。

子任务 4 [50 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成