#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int f[N], nl[N], t[N], n, componente(0), apare[N], sojboi(0);
pair<int, int> v[N];
int radacina(int nod) {
  if (t[nod] == 0) {
    return nod;
  }
  t[nod] = radacina(t[nod]);
  return t[nod];
}
void reuniune(int x, int y) {
  int rx(radacina(x)), ry(radacina(y));
  if (rx == ry) {
    return;
  }
  if (nl[rx] < nl[ry]) {
    t[rx] = ry;
    nl[ry] += nl[rx];
    f[nl[ry]]++;
    f[nl[rx]]--;
    f[nl[ry] - nl[rx]]--;
    if (f[nl[rx]] == 0) {
      --sojboi;
    }
    if (f[nl[ry] - nl[rx]] == 0 && nl[ry] - nl[rx] != nl[rx]) {
      --sojboi;
    }
    if (f[nl[ry]] == 1) {
      ++sojboi;
    }
  } else {
    t[ry] = rx;
    nl[rx] += nl[ry];
    f[nl[rx]]++;
    f[nl[ry]]--;
    f[nl[rx] - nl[ry]]--;
    if (f[nl[ry]] == 0) {
      --sojboi;
    }
    if (f[nl[rx] - nl[ry]] == 0 && nl[rx] - nl[ry] != nl[ry]) {
      --sojboi;
    }
    if (f[nl[rx]] == 1) {
      ++sojboi;
    }
  }
  --componente;
}
void adauga(int poz) {
  ++componente;
  nl[poz] = 1;
  apare[poz] = true;
  f[1]++;
  if (f[1] == 1) {
    ++sojboi;
  }
  if (poz < n && apare[poz + 1]) {
    reuniune(poz, poz + 1);
  }
  if (poz > 1 && apare[poz - 1]) {
    reuniune(poz, poz - 1);
  }
}
int main() {
  int componentemax(-1), valoare(1);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i].first;
    v[i].second = i;
  }
  sort(v + 1, v + n + 1);
  for (int i = 1; i <= n; ++i) {
    adauga(v[i].second);
    while (v[i].first == v[i + 1].first) {
      ++i;
      adauga(v[i].second);
    }
    if (sojboi == 1 && componente > componentemax) {
      componentemax = componente;
      valoare = v[i].first + 1;
    }
  }
  cout << valoare << "\n";
  return 0;
}
