#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100005, LOG = 22;
int n, fth[MaxN], poz[MaxN], fr[MaxN], w[MaxN], sz[MaxN], nrzone = 1;
pair<int, int> v[MaxN];
int Find(int x) {
  if (!fth[x]) return x;
  return fth[x] = Find(fth[x]);
}
void Join(int x, int y) {
  int X = Find(x), Y = Find(y);
  if (X != Y) fth[X] = Y;
}
void Solve(int a, int b) {
  if (a < b) {
    fr[sz[Find(a)]]--;
    fr[sz[Find(b)]]--;
    nrzone--;
    fr[sz[Find(a)] + sz[Find(b)]]++;
    sz[Find(b)] += sz[Find(a)];
    Join(a, b);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i].first;
    w[i] = v[i].first;
    v[i].second = i;
  }
  if (n == 1) {
    cout << v[1].first + 1 << '\n';
    return 0;
  }
  sort(v + 1, v + n + 1);
  v[n + 1].first = v[n].first + 1;
  for (int i = 1; i <= n; ++i) {
    poz[i] = v[i].second;
    w[v[i].second] = i;
  }
  int maxk = 1, nrzonemax = 1;
  fr[1] = 1;
  sz[1] = 1;
  for (int k = 2; k < n; ++k) {
    int pozz = poz[k];
    fr[1]++;
    nrzone++;
    sz[k] = 1;
    if (pozz != 1) Solve(w[pozz - 1], k);
    if (pozz != n) Solve(w[pozz + 1], k);
    if (fr[sz[Find(k)]] == nrzone && nrzone > nrzonemax) {
      maxk = k;
      nrzonemax = nrzone;
    }
  }
  cout << v[maxk].first + 1 << '\n';
  return 0;
}
