#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
pair<int, int> v[N];
set<pair<int, int> > seg;
set<int> sizes;
int cnt[N];
int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &v[i].first);
    v[i].second = i;
  }
  sort(v, v + n, greater<pair<int, int> >());
  int ans = v[0].first + 1;
  seg.insert(pair<int, int>(0, n - 1));
  cnt[n] = 1;
  int best_size = 0;
  for (int i = 0; i < n; i++) {
    auto it = seg.upper_bound(pair<int, int>(v[i].second, v[i].second));
    if (it == seg.end() or it->first > v[i].second) {
      it--;
    }
    pair<int, int> cur = *it;
    seg.erase(it);
    int sz = cur.second - cur.first + 1;
    cnt[sz]--;
    if (cnt[sz] == 0) sizes.erase(sz);
    if (v[i].second == cur.first) {
      if (sz - 1 > 0) {
        seg.insert(pair<int, int>(cur.first + 1, cur.second));
        cnt[sz - 1]++;
        sizes.insert(sz - 1);
      }
    } else if (v[i].second == cur.second) {
      if (sz - 1 > 0) {
        seg.insert(pair<int, int>(cur.first, cur.second - 1));
        cnt[sz - 1]++;
        sizes.insert(sz - 1);
      }
    } else {
      int sz1 = v[i].second - 1 - cur.first + 1;
      int sz2 = cur.second - (v[i].second + 1) + 1;
      if (sz1 > 0) {
        seg.insert(pair<int, int>(cur.first, v[i].second - 1));
        cnt[sz1]++;
        sizes.insert(sz1);
      }
      if (sz2 > 0) {
        seg.insert(pair<int, int>(v[i].second + 1, cur.second));
        cnt[sz2]++;
        sizes.insert(sz2);
      }
    }
    if (sizes.size() == 1 and cnt[*sizes.begin()] >= best_size and i < n - 1) {
      ans = v[i + 1].first + 1;
      best_size = cnt[*sizes.begin()];
    }
  }
  printf("%d\n", ans);
  return 0;
}
