← 返回题目列表

AtCoder · joi2014ho3

C. 年轮蛋糕

中文机器翻译题面 查看原题

配点: 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 。

図 1: バームクーヘンの例 <var>N = 6</var>,<var>A_1 = 1</var>,<var>A_2 = 5</var>,<var>A_3 = 4</var>,<var>A_4 = 5</var>,<var>A_5 = 2</var>,<var>A_6 = 4</var>

给你妹妹打飞机,你在吃年轮蛋糕。 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: <var>1</var> 番目の切れ込みと <var>3</var> 番目の切れ込みと <var>5</var> 番目の切れ込みで切るのが最善である.


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