#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
struct node {
  int x, pos;
  node(int xx = 0, int poss = 0) {
    x = xx;
    pos = poss;
  }
};
node a[maxn];
int num[maxn];
int p[maxn];
int n, tol, dnum, ans, p0, fa[maxn], l[maxn];
int getfa(int x) {
  if (fa[x] == x) return x;
  fa[x] = getfa(fa[x]);
  return fa[x];
}
void link(int x, int y) {
  int fx = getfa(x);
  int fy = getfa(y);
  if (fx != fy) {
    fa[fy] = fx;
    num[l[fx]]--;
    num[l[fy]]--;
    l[fx] += l[fy];
    num[l[fx]]++;
    tol--;
  }
  return;
}
int check(int v, int index) {
  for (int i = index; i <= n && a[i].x < v; i++) {
    int e = a[i].pos;
    if (p[e] == 0) continue;
    p[e] = 0;
    p0 = e;
    tol++;
    num[1]++;
    if (p[e - 1] == 0) link(e, e - 1);
    if (p[e + 1] == 0) link(e, e + 1);
  }
  int r = getfa(p0);
  if (num[l[r]] == tol)
    return tol;
  else
    return -tol;
}
void init() {
  a[0].x = a[n + 1].x = 0;
  ans = dnum = tol = 0;
  for (int i = 0; i <= n + 1; i++) {
    fa[i] = i;
    l[i] = 1;
    p[i] = 1;
    num[i] = 0;
  }
  return;
}
bool cmp(node n1, node n2) { return n1.x < n2.x; }
int main() {
  while (scanf("%d", &n) != EOF) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i].x);
      a[i].pos = i;
    }
    sort(a + 1, a + n + 1, cmp);
    init();
    for (int i = 1; i <= n; i++) {
      if (a[i].x == a[i - 1].x) continue;
      for (int j = 0; j < 2; j++) {
        int cnt = check(a[i].x + j, i);
        if (cnt > dnum) {
          dnum = cnt;
          ans = a[i].x + j;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
