#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000;
long long POW(long long a, long long b, long long MMM = MOD) {
  long long ret = 1;
  for (; b; b >>= 1, a = (a * a) % MMM)
    if (b & 1) ret = (ret * a) % MMM;
  return ret;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) {
  if (a == 0 || b == 0) return a + b;
  return a * (b / gcd(a, b));
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int ddx[] = {0, 0, 1, 1, 1, -1, -1, -1}, ddy[] = {1, -1, 1, 0, -1, 1, 0, -1};
pair<int, int> p[100000];
int cnt[100001];
set<int> leng;
set<pair<int, int> > range;
int main() {
  int n;
  scanf("%d", &n);
  for (int(i) = (0); (i) <= (n - 1); (i) += (1)) {
    scanf("%d", &p[i].first);
    p[i].second = i;
  }
  cnt[n] = 1;
  leng.insert(n);
  range.insert(pair<int, int>(n - 1, 0));
  sort(p, p + n);
  int MAX = 1, ans = p[n - 1].first + 1;
  for (int(i) = (n - 1); (i) >= (1); (i) -= (1)) {
    int t = p[i].second;
    auto it = range.lower_bound(make_pair(t, -1));
    int L, R;
    tie(R, L) = *it;
    range.erase(it);
    cnt[R - L + 1]--;
    if (cnt[R - L + 1] == 0) leng.erase(leng.find(R - L + 1));
    if (L != t) {
      int l = L, r = t - 1;
      range.insert(make_pair(r, l));
      cnt[r - l + 1]++;
      if (cnt[r - l + 1] == 1) leng.insert(r - l + 1);
    }
    if (R != t) {
      int l = t + 1, r = R;
      range.insert(make_pair(r, l));
      cnt[r - l + 1]++;
      if (cnt[r - l + 1] == 1) leng.insert(r - l + 1);
    }
    if (leng.size() == 1) {
      int t = *leng.begin();
      if (cnt[t] > MAX) {
        ans = p[i - 1].first + 1;
        MAX = cnt[t];
      } else if (cnt[t] == MAX)
        ans = p[i - 1].first + 1;
    }
  }
  printf("%d", ans);
}
