#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> p[101000];
long long rar[101000], s[101000], c[101000];
long long root(long long x) {
  while (rar[x] != x) {
    rar[x] = rar[rar[x]];
    x = rar[x];
  }
  return x;
}
int main() {
  long long n, ind, ns = 0, maxi = 0, ans, x, u, v;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    p[i - 1] = make_pair(x, i);
  }
  sort(p, p + n);
  for (int i = 0; i < n; i++) {
    ind = p[i].second;
    if (rar[ind - 1] && rar[ind + 1]) {
      u = root(ind - 1);
      c[s[u]]--;
      v = root(ind + 1);
      c[s[v]]--;
      if (s[u] > s[v]) {
        rar[v] = u;
        s[u] += s[v] + 1;
        rar[ind] = u;
      } else {
        rar[u] = v;
        s[v] += s[u] + 1;
        rar[ind] = v;
      }
      c[s[rar[v]]]++;
      ns--;
    } else if (!rar[ind - 1] && !rar[ind + 1]) {
      rar[ind] = ind;
      s[ind] = 1;
      c[s[ind]]++;
      ns++;
    } else {
      if (rar[ind - 1])
        u = ind - 1;
      else
        u = ind + 1;
      u = root(u);
      c[s[u]]--;
      rar[ind] = u;
      s[u]++;
      c[s[u]]++;
    }
    if (c[s[root(ind)]] == ns) {
      if (ns > maxi) {
        maxi = ns;
        ans = p[i].first + 1;
      }
    }
  }
  cout << ans << endl;
}
