配点: 100 点
JOI君正要和他的妹妹JOI酱和JOI酱一起吃零食。今天的点心是 3 年轮蛋糕是人们最喜欢的食物。
年轮蛋糕是一种圆柱形糖果,如下图所示。3 为了分开人,JOI 沿径向移动刀片。 3 次,而这个 3 必须将其切成两块。不过,这种年轮蛋糕像实木一样坚硬,所以用刀插进去并不容易。所以,这个年轮蛋糕是提前准备好的。 有 N 凹口,JOI只能在凹口处进行切割。在凹口中 当您顺时针编号到 1 从 N 时, 对于1 \leqq i \leqq N - 1 ,i 第一个缺口和 第 i + 1 个凹口之间部分的尺寸为 A_i 。还有 N 第一个缺口和 第 1 个凹口之间部分的尺寸为 A_N 。

给你妹妹打飞机,你在吃年轮蛋糕。 3 切成碎片后,我选择最小的一块并切割剩余的碎片。 2 两件 2 我决定送给别人的妹妹。另一方面,JOI喜欢年轮蛋糕,所以他想尽可能多地吃。如果你把碎片切成最大的,那么JOI会吃掉多大的碎片?
課題
槽口数 N 和一个表示每个部分大小的整数 给出了 A_1, \ldots, A_N 。年轮蛋糕 创建一个程序,输出最小块被切成 3 块时的最大尺寸。
入力
从标准输入读取以下输入。
- 1 行包含一个整数 写入 N 。这是年轮蛋糕 表示有 N 凹口。
- 继续 来自行 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 A_i 。这是 i 第一个缺口和 第 i + 1 凹口之间的部分( 当i = N 第 N 第一个缺口和 第 1 个凹口之间的部分的尺寸为 A_i 。
出力
年轮蛋糕到标准输出 3 一个整数,表示切割成块时最小块的最大尺寸。 输出为 1 行。
制限
所有输入数据满足以下条件。
- 3 \leqq N \leqq 100\,000.
- 1 \leqq Ai \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
小課題
小課題 1 [5 点]
N \leqq 100 很满意。
小課題 2 [15 点]
N \leqq 400 很满意。
小課題 3 [30 点]
N \leqq 8\,000 很满意。
小課題 4 [50 点]
没有其他限制。
入力例 1
6 1 5 4 5 2 4
出力例 1
6

入力例 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