CF982D.Shark

For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For $n$ days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer $k$ that if the shark in some day traveled the distance strictly less than $k$, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to $k$; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least $k$.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of $n$ days we can find consecutive nonempty segments when the shark traveled the distance less than $k$ in each of the days: each such segment corresponds to one location. Max wants to choose such $k$ that the lengths of all such segments are equal.

Find such integer $k$, that the number of locations is as large as possible. If there are several such $k$, print the smallest one.

长期以来，科学家们一直在研究鲨鱼的行为。与其他许多物种一样，鲨鱼会在某个地点进行短距离移动，然后在不同地点之间进行长距离移动。

马克斯是一名年轻的生物学家。他连续观察了某条鲨鱼 $n$ 天，并记录下了鲨鱼每天所游过的距离。所有这些距离互不相同。现在，马克斯希望推断出这条鲨鱼一共访问了多少个不同的地点。他假设存在一个整数 $k$，使得：若鲨鱼某天游过的距离严格小于 $k$，则它当天没有更换地点；反之，若某天游过的距离大于等于 $k$，则它当天更换了地点。注意，鲨鱼有可能连续多天都在更换地点，即这些天中每天游过的距离均至少为 $k$。

此外，鲨鱼一旦离开某个地点，就永远不会返回该地点。因此，在这 $n$ 天的序列中，我们可以找出若干段非空的连续区间，其中每一段内每一天鲨鱼游过的距离都小于 $k$；每一段这样的区间对应鲨鱼停留的一个地点。马克斯希望选择一个 $k$，使得所有这些区间的长度都相等。

请找出满足上述条件的整数 $k$，使得鲨鱼访问的地点数量尽可能多。如果有多个这样的 $k$，输出其中最小的一个。

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of days.

The second line contains $n$ distinct positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the distance traveled in each of the day.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示天数。

第二行包含 $n$ 个互不相同的正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）—— 表示每天行驶的距离。

Print a single integer $k$, such that

1. the shark was in each location the same number of days,
2. the number of locations is maximum possible satisfying the first condition,
3. $k$ is smallest possible satisfying the first and second conditions.

输出一个整数 $k$，使得：

1. 鲨鱼在每个位置停留的天数相同；
2. 在满足第一条条件的前提下，位置的数量尽可能多；
3. 在满足第一条和第二条条件的前提下，$k$ 尽可能小。

In the first example the shark travels inside a location on days $1$ and $2$ (first location), then on $4$-th and $5$-th days (second location), then on $7$-th and $8$-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the $2$-nd day, so there is only one location.

在第一个例子中，鲨鱼在第 $1$ 天和第 $2$ 天（第一个位置）、第 $4$ 天和第 $5$ 天（第二个位置）、第 $7$ 天和第 $8$ 天（第三个位置）分别停留在某一位置内。总共有三个位置。

在第二个例子中，鲨鱼仅在第 $2$ 天停留在某一位置内，因此只有一个位置。