题目描述

在 Berland，反对派打算在林荫大道上举行大规模游行。这条林荫大道由 $n$ 块依次排列的地砖组成，从右到左编号为 $1$ 到 $n$。反对派应当从编号为 $1$ 的地砖出发，最终到达编号为 $n$ 的地砖。在游行过程中，允许从一块地砖移动到左边相邻的下一块地砖，也可以跳过一块地砖，即如果你在第 $i$ 块地砖上（$i<n-1$），可以到达第 $i+1$ 块或第 $i+2$ 块地砖（如果你在第 $n-1$ 块地砖上，只有到达第 $n$ 块地砖的方式）。可以认为所有的移动都是瞬时完成的。

为了阻挠反对派的集会，Berland 的血腥政权组织了降雨。这些林荫大道上的地砖质量很差，在雨中会很快损坏。已知第 $i$ 块地砖在下雨 $a_i$ 天后会损坏（在第 $a_i$ 天还是完好无损的，在第 $a_i+1$ 天就已经损坏了）。显然，任何人都不能踏上已经损坏的地砖！因此，如果第 $1$ 块地砖损坏了，或者第 $n$ 块地砖损坏了，或者从第 $1$ 块地砖无法到达第 $n$ 块地砖（只能在未损坏的地砖间行走），就认为游行被阻挠了。

反对派希望能有更多的时间聚集更多支持者，因此他们准备时间越多越好。请你帮反对派算出，他们还剩下多少天可以游行，也就是说，从编号为 $1$ 的地砖到编号为 $n$ 的地砖之间，最多还能保持多少天可以顺利通行。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^{3}$），表示林荫大道的长度。

第二行包含 $n$ 个用空格分隔的整数 $a_i$，表示第 $i$ 块地砖在下雨 $a_i$ 天后会损坏（$1 \leq a_i \leq 10^{3}$）。

输出格式

输出一个整数，表示从第 $1$ 块地砖到第 $n$ 块地砖，最多还能保持多少天可行走。

说明/提示

在第一个样例中，第 2 块地砖在第 3 天后损坏，此时唯一的可行路径是 $1\to3\to4$。在第 5 天后，第 1 块与最后一块地砖之间出现了两个地砖的空隙，已经无法跨越。

在第二个样例中，路径 $1\to3\to5$ 在第 5 天仍然可行。在第 6 天时，最后一块地砖损坏，游行被阻挠。

由 ChatGPT 5 翻译

样例

4
10 3 5 10

5

5
10 2 8 3 5

5