AT_joi2014ho3 バームクーヘン (Baumkuchen)

JOI 君打算和他的妹妹 JOI 子酱以及 JOI 美酱一起吃点心。今天的点心是三个人都非常喜欢的年轮蛋糕。 年轮蛋糕是一种如图所示的圆柱形点心。为了将其分成三份，JOI 君需要沿着半径方向切三刀，将其切成三块。不过，这个年轮蛋糕像真正的木头一样坚硬，所以切起来并不容易。因此，年轮蛋糕上预先有 $N$ 个切口，JOI 君只能在这些切口处切割。将这些切口按顺时针方向编号为 $1$ 到 $N$，对于 $1 \leq i \leq 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 君很关心他的妹妹们，所以在将年轮蛋糕切成三块后，他会选择最小的一块自己吃，把剩下的两块分给两个妹妹。另一方面，JOI 君非常喜欢年轮蛋糕，所以他希望自己能吃到尽可能多的蛋糕。请问，当最小的一块的大小最大时，JOI 君能吃到的蛋糕块的大小是多少？

从标准输入读取如下内容。 - 第 $1$ 行包含一个整数 $N$，表示年轮蛋糕上有 $N$ 个切口。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含一个整数 $A_i$，表示第 $i$ 个切口和第 $i+1$ 个切口之间部分的大小（当 $i=N$ 时，表示第 $N$ 个切口和第 $1$ 个切口之间部分的大小）。

请输出将年轮蛋糕分成三块时，最小一块的最大可能大小。输出一个整数。

## 任务 给定切口数量 $N$ 和各部分的大小 $A_1,\ldots,A_N$，请编写程序输出将年轮蛋糕分成三块时，最小一块的最大可能大小。 ## 限制 所有输入数据满足以下条件： - $3 \leq N \leq 100\,000$。 - $1 \leq A_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。 ## 子任务 ### 子任务 1 [5 分] 满足 $N \leq 100$。 ### 子任务 2 [15 分] 满足 $N \leq 400$。 ### 子任务 3 [30 分] 满足 $N \leq 8\,000$。 ### 子任务 4 [50 分] 无额外限制。 ## 样例解释 1  图 2：在第 $1$、$3$、$5$ 个切口处切割是最优的。 由 ChatGPT 4.1 翻译