#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const long long linf = (long long)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n;
int a[N];
set<int> ev;
int total, cmp;
int cnt[N];
int p[N], len[N], sz[N];
bool dbg;
int get(int x) {
  if (p[x] == x) return x;
  return p[x] = get(p[x]);
}
void add(int v) {}
void merge(int v, int u) {
  v = get(v), u = get(u);
  if (v == u) return;
  cmp--;
  cnt[len[v]]--;
  if (!cnt[len[v]]) total--;
  cnt[len[u]]--;
  if (!cnt[len[u]]) total--;
  if (!cnt[len[v] + len[u]]) total++;
  cnt[len[v] + len[u]]++;
  if (sz[v] > sz[u])
    p[u] = v, len[v] += len[u];
  else if (sz[v] < sz[u])
    p[v] = u, len[u] += len[v];
  else {
    p[v] = u;
    len[u] += len[v];
    sz[u]++;
  }
}
void make(int id) {
  len[id] = 1;
  if (!cnt[len[id]]) total++;
  cnt[1]++;
  p[id] = id;
  sz[id] = 1;
  cmp++;
}
void go(int id) {
  make(id);
  if (id == 2) dbg = 1;
  if (p[id - 1]) {
    merge(id - 1, id);
  }
  if (p[id + 1]) merge(id + 1, id);
}
int main() {
  ios_base ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  set<pair<int, int> > st;
  for (int i = (1); i <= (n); i++) {
    cin >> a[i];
    ev.insert(a[i] + 1);
    st.insert({a[i], i});
  }
  int mx = 0, ans = st.begin()->first + 1;
  for (auto it : ev) {
    while ((int)st.size() && st.begin()->first < it) {
      go(st.begin()->second);
      st.erase(st.begin());
    }
    if (total == 1) {
      if (cmp > mx) {
        mx = cmp;
        ans = it;
      }
    }
  }
  cout << ans;
  exit(0);
}
