← 返回题目列表

Codeforces · 955/E

E. 冰柱

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

安德鲁最喜欢的克拉科兹亚布拉最近逃走了,现在他渴望把它带回来!

目前,难民位于一个冰冷的洞穴内,天花板上悬挂着 n 个冰柱,位于编号为 1 到 n 的整数坐标中。地板和第 i 个冰柱之间的距离等于 ai。

安德鲁可以自由选择从1到n(含)范围内的任意整数点T,并在时刻0发射声波,以每秒一个点的速度向两侧(左和右)传播。任何被波接触到的冰柱都开始以相同的速度下落(这意味着在一秒钟内从地板到冰柱的距离减少一,但不能小于零)。当冰柱到地板的距离大于零时,认为可以通过;一旦变为零,冰柱就会挡住路径并禁止通过。

Krakozyabra 最初(即在时刻 0)位于点 $$\frac{1}{2}$$ 并开始以每秒一点的速度沿正确的方向运行。你可以假设一秒钟内的事件按照以下顺序发生:首先克拉科兹亚布拉改变位置,然后声音传播,冰柱落下;然后,克拉科兹亚布拉改变位置,然后声音传播,冰柱落下;特别是,这意味着如果 Krakozyabra 当前位于 $$i-\frac{1}{2}$$ 点,并且 i 点下落(即已经被声波触及)的冰柱距离地面 1 点,那么 Krakozyabra 将经过它并发现自己位于 $$i + \frac{1}{2}$$ 处,只有在此之后,冰柱才会最终落下并阻挡路径。

如果 Krakozyabra 当前位置的左侧和右侧都有掉落的(即 ai = 0)冰柱,则认为 Krakozyabra 已被困住。通过选择 T 的最佳值,帮助 Andrew 找到诱捕 Krakozyabra 所需的最短时间,或者报告此任务是不可能的。

输入

第一行包含冰柱数量 n (2 ≤ n ≤ 105)。

下一行包含 n 个空格分隔的数字 ai (1 ≤ ai ≤ 105) - 从地板到冰柱的距离。

输出

打印一个唯一的整数——将 Krakozyabra 困在两个掉落的冰柱之间所需的最短时间。如果不可能,则打印 - 1。

示例

输入 #1

5
1 4 3 5 1

输出 #1

3

输入 #2

4
1 2 1 1

输出 #2

2

输入 #3

2
2 1

输出 #3

3

输入#4

2
1 2

输出#4

-1

注意

在示例案例一中,最佳方案是从点 3 发射声波。然后,两秒后,冰柱 1 和 5 将开始掉落,再过一秒,它们将阻塞路径。 Krakozyabra 届时将位于 $$3\frac{1}{2}$$。请注意,3 号冰柱也会掉落,因此实际上会有两根冰柱挡住了左侧的路径。

在示例案例 2 中,最佳选择是从点 2 发射波浪并在 2 秒内捕获 Krakozyabra。

在示例案例四中,答案是不可能的。