#include <bits/stdc++.h>
using namespace std;
int n, num, ans, mx, b[200005], cnt;
struct he {
  int d, p;
} a[200005];
struct tree {
  int l, r;
} tr[200005 * 4];
bool cmp(he a, he b) { return a.d > b.d; }
void insert(int p, int l, int r, int x, int y, int ll, int rr) {
  if (y < x) return;
  if (x > r || l > y) return;
  if (x <= l && r <= y) {
    tr[p].l = ll;
    tr[p].r = rr;
    return;
  }
  if (tr[p].l != 0) {
    tr[p * 2].l = tr[p * 2 + 1].l = tr[p].l;
    tr[p * 2].r = tr[p * 2 + 1].r = tr[p].r;
    tr[p].l = tr[p].r = 0;
  }
  int mid = (l + r) / 2;
  insert(p * 2, l, mid, x, y, ll, rr);
  insert(p * 2 + 1, mid + 1, r, x, y, ll, rr);
}
void get(int p, int l, int r, int x, int &ll, int &rr) {
  if (x > r || l > x) return;
  if (x == l && r == x) {
    ll = tr[p].l;
    rr = tr[p].r;
    return;
  }
  if (tr[p].l != 0 || tr[p].r != 0) {
    tr[p * 2].l = tr[p * 2 + 1].l = tr[p].l;
    tr[p * 2].r = tr[p * 2 + 1].r = tr[p].r;
    tr[p].l = tr[p].r = 0;
  }
  int mid = (l + r) / 2;
  get(p * 2, l, mid, x, ll, rr);
  get(p * 2 + 1, mid + 1, r, x, ll, rr);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i].d), a[i].p = i;
  sort(a + 1, a + 1 + n, cmp);
  insert(1, 1, n, 1, n, 1, n);
  b[n] = 1;
  cnt = 1;
  num = mx = 1;
  ans = a[1].d + 1;
  for (int i = 1; i <= n; i++) {
    int l, r;
    get(1, 1, n, a[i].p, l, r);
    b[r - l + 1]--;
    if (b[r - l + 1] == 0) cnt--;
    num++;
    if (l == a[i].p)
      num--;
    else {
      insert(1, 1, n, l, a[i].p - 1, l, a[i].p - 1);
      b[a[i].p - 1 - l + 1]++;
      if (b[a[i].p - 1 - l + 1] == 1) cnt++;
    }
    if (r == a[i].p)
      num--;
    else {
      insert(1, 1, n, a[i].p + 1, r, a[i].p + 1, r);
      b[r - (a[i].p + 1) + 1]++;
      if (b[r - (a[i].p + 1) + 1] == 1) cnt++;
    }
    if (a[i + 1].d == a[i].d) continue;
    if (cnt == 1) {
      if (num == mx)
        ans = min(ans, a[i + 1].d + 1);
      else if (num > mx) {
        mx = num;
        ans = a[i + 1].d + 1;
      }
    }
  }
  printf("%d\n", ans);
}
