T4 奇怪游戏

时间：$1s$

空间：$256M$

题目描述

小$W$ 和 小$Z$ 正在玩一个奇怪的游戏。

他们有一个长度为 $n$ 的整数数组 $a_1,a_2,a_3,...,a_n$，首先小 $W$ 选择一个整数 $k$，要求满足 小$Z$ 选择任意连续区间（区间长度至少为 $2$）内的最大值都要大于 $k$。求满足要求的，小$W$ 能选的最大整数 $k$。

让上面条件更具体化一些，即：

• 小$Z$ 选择两个整数 $i$ 和 $j$ $(1≤𝑖<𝑗≤𝑛)$，从 $a_i,a_{i+1},...a_j$ 中找到最大值
• 获得的最大值需要大于 $k$

输入格式

第一行包含一个正整数 $n$ $(2≤𝑛≤5\times10^5)$，表示数组中元素个数。

第二行包含 $n$ 个正整数 $a_1,a_2,a_3,...,a_n$（$1≤a_i≤10^9$）

输出格式

输出一行一个整数表示小$W$ 能选的最大整数 $k$。

样例

4
2 4 1 7

3

3
37 8 16

15

10
3 12 9 5 2 3 2 9 8 2

2

样例提示

样例 $1$ ：小$Z$ 可以选择的连续区间为 $[2,4],[2,4,1],[2,4,1,7],[4,1],[4,1,7],[1,7]$，子段上的最大值分别等于 $4,4,7,4,7,7$ 。可以证明 $3$ 是最大整数，因此任何最大值都严格大于它。