Remove Extra One

题意:[1..n]的排列a. 定义a[i]合法:当所有j (1<=j<i)都满足a[j]<a[i].
n<=1e5.删除一个数之后 要使得排列a的合法个数最多 输出要删除的哪一个数.若有多解,输出最小的解.

The first line contains the only integer n (1 ≤ n ≤ 10⁵) — the length of the permutation.

The second line contains n integers p₁, p₂, ..., p_n (1 ≤ p_i ≤ n) — the permutation. All the integers are distinct.

Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

1
1

1

5
5 1 2 3 4

5

 Note

In the first example the only element can be removed.