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

We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai. 

Input

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

The second line contains n integers p1, p2, ..., pn (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.

Examples

Input

1
1


Output

1


Input

5
5 1 2 3 4


Output

5

Note

In the first example the only element can be removed.
#include <bits/stdc++.h>
using namespace std;
long long int fir[100009][2];
long long int sec[100009][2];
long long int dp[100009];
long long int fp[100009] = {0};
long long int f[100009] = {0};
int main() {
  long long int n;
  cin >> n;
  long long int a[n + 1];
  for (long long int i = 0; i <= n - 1; ++i) cin >> a[i];
  if (n == 1) {
    cout << a[0] << endl;
    return 0;
  }
  fir[0][0] = a[0];
  fir[0][1] = 0;
  sec[0][0] = -1;
  sec[0][1] = -1;
  if (a[1] > a[0]) {
    fir[1][0] = a[1];
    fir[1][1] = 1;
    sec[1][0] = a[0];
    sec[1][1] = 0;
  } else {
    fir[1][0] = a[0];
    fir[1][1] = 0;
    sec[1][0] = a[1];
    sec[1][1] = 1;
  }
  for (long long int i = 2; i <= n - 1; ++i) {
    if (a[i] > fir[i - 1][0]) {
      fir[i][0] = a[i];
      fir[i][1] = i;
      sec[i][0] = fir[i - 1][0];
      sec[i][1] = fir[i - 1][1];
    } else {
      if (a[i] > sec[i - 1][0]) {
        fir[i][0] = fir[i - 1][0];
        fir[i][1] = fir[i - 1][1];
        sec[i][0] = a[i];
        sec[i][1] = i;
      } else {
        fir[i][0] = fir[i - 1][0];
        fir[i][1] = fir[i - 1][1];
        sec[i][0] = sec[i - 1][0];
        sec[i][1] = sec[i - 1][1];
      }
    }
  }
  dp[0] = 0;
  for (long long int i = 1; i <= n - 1; ++i) {
    if (fir[i][0] == a[i]) {
      dp[i] = dp[i - 1] + 1;
    } else {
      dp[i] = dp[i - 1];
    }
  }
  if (fir[n - 1][0] == a[n - 1]) {
    fp[n - 1] = 1;
  }
  for (long long int i = n - 2; i >= 0; i--) {
    if (fir[i][0] == a[i]) {
      fp[i] = 1 + fp[i + 1];
    } else {
      fp[i] = fp[i + 1];
    }
  }
  for (long long int i = 1; i <= n - 1; ++i) {
    if (sec[i][0] == a[i]) {
      f[fir[i][1]]++;
    }
  }
  if (a[0] > a[1]) {
    f[0]--;
  }
  long long int ans = 0;
  long long int val = 0;
  for (long long int i = 1; i <= n - 2; ++i) {
    if (ans < f[i] + fp[i + 1] + dp[i - 1]) {
      ans = f[i] + fp[i + 1] + dp[i - 1];
      val = a[i];
    } else if (ans == f[i] + fp[i + 1] + dp[i - 1]) {
      if (val > a[i] || val == 0) {
        val = a[i];
      }
    }
  }
  if (ans < dp[n - 2]) {
    ans == dp[n - 2];
    val = a[n - 1];
  } else if (ans == dp[n - 2]) {
    if (val > a[n - 1] || val == 0) {
      val = a[n - 1];
    }
  }
  if (a[1] > a[0]) {
    if (ans < fp[1] - 1) {
      ans = fp[1] - 1;
      val = a[0];
    } else if (ans == fp[1] - 1) {
      if (val > a[0] || val == 0) {
        val = a[0];
      }
    }
  } else {
    if (ans < fp[1] + f[0]) {
      ans = fp[1] + f[0];
      val = a[0];
    } else if (ans == fp[1] + f[0]) {
      if (val > a[0] || val == 0) {
        val = a[0];
      }
    }
  }
  cout << val << endl;
  return 0;
}
