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;
const long long mxN = 200000;
vector<long long> adj[mxN];
template <class T>
struct Seg {
  const T ID = 0;
  T comb(T a, T b) { return max(a, b); }
  long long n;
  vector<T> seg;
  void init(long long _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }
  void pull(long long p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
  void upd(long long p, T val) {
    seg[p += n] = val;
    for (p /= 2; p; p /= 2) pull(p);
  }
  T query(long long l, long long r) {
    T ra = ID, rb = ID;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) ra = comb(ra, seg[l++]);
      if (r & 1) rb = comb(seg[--r], rb);
    }
    return comb(ra, rb);
  }
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  long long a[n];
  for (long long i = 0; i < n; ++i) {
    cin >> a[i];
  }
  Seg<long long> b;
  b.init(n + 1);
  for (long long i = 0; i < n; ++i) {
    b.upd(i, a[i]);
  }
  long long c[n][2];
  for (long long i = 0; i < n; ++i) {
    c[i][0] = c[i][1] = -1;
  }
  for (long long i = 0; i < n - 1; ++i) {
    if (b.query(i + 1, n - 1) < a[i]) continue;
    long long l = i + 1, r = n - 1;
    while (l < r) {
      long long m = l + (r - l) / 2;
      if (b.query(i + 1, m) < a[i]) {
        l = m + 1;
      } else {
        r = m;
      }
    }
    long long fl = l;
    c[i][0] = fl;
    b.upd(fl, 0);
    if (b.query(i + 1, n - 1) < a[i]) {
      b.upd(fl, a[fl]);
      continue;
    }
    l = i + 1, r = n - 1;
    while (l < r) {
      long long m = l + (r - l) / 2;
      if (b.query(i + 1, m) < a[i]) {
        l = m + 1;
      } else {
        r = m;
      }
    }
    c[i][1] = l;
    b.upd(fl, a[fl]);
  }
  for (long long i = 0; i < n; ++i) {
    if (c[i][0] == -1) continue;
    adj[i].push_back(c[i][0]);
    adj[i + n].push_back(c[i][0] + n);
    if (c[i][1] == -1) continue;
    adj[i].push_back(c[i][1] + n);
  }
  queue<array<long long, 3>> q;
  q.push({0, 1, -1});
  q.push({n + 1, 1, 0});
  long long ans = 1;
  long long arem = 0;
  while (q.size()) {
    auto [node, dist, rem] = q.front();
    q.pop();
    if (dist > ans ||
        (dist == ans && rem != -1 && arem != -1 && a[arem] > a[rem]) ||
        (dist == ans && rem == -1)) {
      ans = dist;
      arem = rem;
    }
    for (long long i : adj[node]) {
      long long nrem = -1;
      if (node < n && i >= n) nrem = c[node][0];
      if (rem != -1) nrem = rem;
      q.push({i, dist + 1, nrem});
    }
  }
  if (arem == -1) {
    long long mx = 0;
    long long mn = 1e9, mni = -1;
    for (long long i = 0; i < n; ++i) {
      if (a[i] < mx) {
        if (a[i] < mn) {
          mn = a[i];
          mni = i;
        }
      }
      mx = max(mx, a[i]);
    }
    arem = mni;
  }
  if (arem == -1) {
    arem = 0;
    bool all = 1;
    for (long long i = 0; i < n; ++i) {
      all &= a[i] == i + 1;
    }
    assert(all);
  }
  cout << a[arem] << '\n';
}
