#include <bits/stdc++.h>
using namespace std;
int n;
int a[100008];
map<int, int> mapa;
map<int, int> mapb;
map<int, int> mapc;
int vis[100008];
int main() {
  int ansa = -1;
  int ansk = 1000000008;
  int nowa = 1;
  scanf("%d", &n);
  vis[0] = 1;
  vis[n + 1] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    mapa[a[i]] = i;
  }
  mapb[1] = n;
  mapc[n]++;
  for (auto it = --mapa.end();;) {
    auto itb = mapb.upper_bound(it->second);
    itb--;
    if (itb->first + itb->second - it->second - 1 > 0) {
      mapc[itb->first + itb->second - it->second - 1]++;
      mapb[it->second + 1] = itb->first + itb->second - it->second - 1;
    }
    if (itb->first != it->second) {
      mapc[itb->second]--;
      if (mapc[itb->second] == 0) {
        mapc.erase(itb->second);
      }
      mapc[it->second - itb->first]++;
      itb->second = it->second - itb->first;
    } else {
      mapc[itb->second]--;
      if (mapc[itb->second] == 0) {
        mapc.erase(itb->second);
      }
      mapb.erase(itb->first);
    }
    if (vis[it->second - 1] == 0 && vis[it->second + 1] == 0) {
      nowa++;
    } else if (vis[it->second - 1] == 1 && vis[it->second + 1] == 1) {
      nowa--;
    }
    vis[it->second] = 1;
    if (mapc.size() == 1) {
      if (nowa > ansa) {
        ansa = nowa;
        ansk = it->first;
      } else if (nowa == ansa) {
        ansk = min(ansk, it->first);
      }
    }
    if (it == mapa.begin()) {
      break;
    }
    it--;
  }
  auto itk = mapa.lower_bound(ansk);
  itk--;
  ansk = itk->first + 1;
  printf("%d\n", ansk);
  return 0;
}
