Remove Extra One

You are given a permutation p p p of length n n n. Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers a 1 , a 2 , … , a k a_1,a_2,\dots,a_k a1​,a2​,…,ak​ the element a i a_i ai​ is a record if for every integer j j j ( 1   ≤   j   <   i 1 \leq j < i 1 ≤ j < i) the following holds: a j   <   a i a_j < a_i aj​ < ai​.

Input

The first line contains the only integer n n n ( 1   ≤   n   ≤   1 0 5 1 \leq n \leq 10^5 1 ≤ n ≤ 105) — the length of the permutation.

The second line contains n n n integers p 1 ,   p 2 ,   … ,   p n p_1, p_2, \dots, p_n p1​, p2​, …, pn​ ( 1   ≤   p i   ≤   n 1 \leq p_i \leq n 1 ≤ pi​ ≤ n) — the permutation. All the integers are distinct.

Output

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.

Example

Note

In the first example the only element can be removed.

Tutorial

不妨转换一下题意：删除一个元素后，有多少位置的数值等于前缀最大值

所以可以对每一个位置进行计数，对于删去 x x x 后，需要记录

• 哪些位置在删去 x x x 后变成了前缀最大值，即该值前面只有 x x x 这个数比该位置的数大
• 哪些位置在删去 x x x 后不再是前缀最大值，即删除前 x x x 就是前缀最大值

  根据上面两种情况，我们可以计算每个元素删去时，满足条件的位置数值会发生怎样的变化，最后取最大值即可

  此解法时间复杂度为 O ( n ) \mathcal O(n) O(n)

  Solution

  #include 
  using namespace std;
  signed main() {
      int n, ans = 0;
      cin >> n;
      vector p(n), mx(2, -1), mid(n);
      for (int i = 0; i < n; ++i) {
          cin >> p[i];
          if (mx[0] == -1 or p[i] > p[mx[0]]) { // 是否为最大值
              mid[i]--;
              mx[1] = mx[0];
              mx[0] = i;
          } else if (mx[1] == -1 or p[i] > p[mx[1]]) { // 是否仅小于最大值
              mid[mx[0]]++;
              mx[1] = i;
          }
      }
      for (int i = 0; i < n; ++i) {
          if (mid[i] > mid[ans] or (mid[i] == mid[ans] and p[i] < p[ans])) {
              ans = i;
          }
      }
      cout << p[ans] << endl;
      return 0;
  }