#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int mxN = 1e5 + 5;
template <class T>
T gcd(T a, T b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
int cnt[mxN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, vector<int> > m;
  set<int> st1;
  int mx = 0;
  for (int i = 0; i < (int)(n); i++)
    cin >> a[i], m[a[i]].push_back(i), mx = max(mx, a[i]), st1.insert(a[i]);
  vector<int> pos(st1.begin(), st1.end());
  reverse(pos.begin(), pos.end());
  set<int> st;
  st.insert(-1);
  st.insert(n);
  cnt[n] = 1;
  int num = 1;
  int lst = 1;
  int ans = mx + 1;
  int bst = 1;
  for (int j = 0; j < (int)(pos.size()); j++) {
    vector<int> cur = m[pos[j]];
    for (int i = 0; i < (int)(cur.size()); i++) {
      auto it = st.lower_bound(cur[i]);
      auto it1 = it;
      it1--;
      num--;
      cnt[(*it - *it1) - 1]--;
      if (!cnt[((*it - *it1) - 1)]) lst--;
      if ((cur[i] - *it1) > 1) {
        num++;
        if (!cnt[(cur[i] - *it1 - 1)]) lst++;
        cnt[(cur[i] - *it1 - 1)]++;
      }
      if ((*it - cur[i]) > 1) {
        num++;
        if (!cnt[(*it - cur[i] - 1)]) lst++;
        cnt[(*it - cur[i] - 1)]++;
      }
      st.insert(cur[i]);
    }
    if (lst == 1 && num >= bst) {
      ans = pos[j];
      if (j != (pos.size() - 1)) ans = pos[j + 1] + 1;
      bst = num;
    }
  }
  cout << ans << endl;
  return 0;
}
