#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
int pre[N], sz[N], cnt[N], n, lencnt, dx, one;
pair<int, int> a[N];
void init() { memset(pre, -1, sizeof(pre)); }
int fd(int n) { return pre[n] == -1 ? n : pre[n] = fd(pre[n]); }
void mg(int a, int b) {
  a = fd(a), b = fd(b);
  if (a != b) {
    pre[b] = a;
    sz[a] += sz[b];
    sz[b] = 0;
  }
}
void solve(int x) {
  int v = x + 1;
  if (v <= n && sz[fd(v)]) {
    if (--cnt[sz[fd(v)]] == 0) --lencnt;
    if (--cnt[sz[x]] == 0) --lencnt;
    mg(x, v);
    if (++cnt[sz[fd(v)]] == 1) ++lencnt;
  }
  v = x - 1;
  if (v >= 1 && sz[fd(v)]) {
    if (--cnt[sz[fd(v)]] == 0) --lencnt;
    if (--cnt[sz[fd(x)]] == 0) --lencnt;
    mg(x, v);
    if (++cnt[sz[fd(v)]] == 1) ++lencnt;
  }
  one = cnt[sz[fd(x)]];
}
int main(void) {
  int i;
  scanf("%d", &n);
  init();
  for (i = 1; i <= n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a + 1, a + 1 + n);
  int ans = 1;
  for (i = 1; i <= n; ++i) {
    sz[a[i].second] = 1;
    if (++cnt[1] == 1) ++lencnt;
    solve(a[i].second);
    if (lencnt == 1 && one > dx) {
      ans = a[i].first + 1;
      dx = one;
    }
  }
  printf("%d\n", ans);
  return 0;
}
