← 返回题目列表

Codeforces · 192/B

B. 雨中行走

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

在伯兰,反对派将安排群众在林荫大道上行走。林荫大道由 n 块排成一排的瓷砖组成,从右到左编号为 1 到 n。对手应从 1 号牌开始行走,并在 n 号牌上结束。在行走过程中,它可以在一行相邻的瓷砖之间从右向左移动,并跳过一块瓷砖。更正式地说,如果你站在第 i 号图块上(i < n - 1),你可以从中到达第 i + 1 号图块或第 i + 2 号图块(如果你站在第 n - 1 号图块上,你只能到达第 n 号图块)。我们可以假设所有的反对运动都是瞬间发生的。

为了挫败反对派集会,贝尔兰血腥政权组织了一场雨。大道上的瓷砖质量很差,在雨中很快就被毁坏了。我们知道,第 i 个瓷砖在 ai 天的雨后被破坏(在 ai 天的雨天,它还没有被破坏,而在 ai + 1 天,它已经被破坏了)。当然,任何人都不可以在被破坏的瓷砖上行走!因此,如果 1 号瓷砖被破坏,或者 n 号瓷砖被破坏,或者如果我们可以在未损坏的瓷砖上行走,则不可能从 1 号瓷砖到达 n 号瓷砖,则对手的行走被视为受挫。

反对派希望为他们的游行聚集更多支持者。因此,他们收拾行李的时间越多越好。帮助对手计算他们还剩下多少时间,并告诉我们从 1 号格走到 n 号格需要多少天。

输入

第一行包含整数 n (1 ≤ n ≤ 103) — 林荫大道的长度(以图块为单位)。

第二行包含 n 个空格分隔的整数 ai — 第 i 个图块被销毁之前的天数 (1 ≤ ai ≤ 103)。

输出

打印一个数字 — 所需的天数。

示例

输入 #1

4
10 3 5 10

输出 #1

5

输入 #2

5
10 2 8 3 5

输出 #2

5

注意

在第一个示例中,第三天后第二个图块被摧毁,剩下的唯一路径是 1 → 3 → 4。第五天后,第一个和最后一个图块之间有两个图块间隙,您无法跳过它。

在第二个示例路径中,1 → 3 → 5 在第五天(含)之前可用。第六天,最后一块瓷砖被毁,步行也受阻。