#include <bits/stdc++.h>
using namespace std;
int pai[100005], sz[100005], v[100005];
set<pair<int, int> > s;
set<int> ordem;
map<int, vector<int> > m;
void remove(int n) {
  pair<int, int> aux = *(s.lower_bound(make_pair(n, -0x3F3F3F3F)));
  s.erase(aux);
  if (aux.second > 1) s.insert(make_pair(n, aux.second - 1));
}
void add(int n) {
  pair<int, int> aux = *(s.lower_bound(make_pair(n, -0x3F3F3F3F)));
  if (aux.first == n) {
    s.erase(aux);
    s.insert(make_pair(n, aux.second + 1));
  } else
    s.insert(make_pair(n, 1));
}
int query(int A) {
  if (pai[A] == A) return A;
  return pai[A] = query(pai[A]);
}
bool same(int A, int B) { return query(A) == query(B); }
void join(int A, int B) {
  int x = query(A), y = query(B);
  if (sz[x] > 1) remove(sz[x]);
  remove(sz[y]);
  pai[y] = x;
  sz[x] += sz[y], sz[y] = 0;
  add(sz[x]);
}
int main() {
  int n, i, j, pos;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    pai[i] = i;
    sz[i] = 1;
    scanf("%d", &v[i]);
    ordem.insert(v[i]);
    m[v[i]].push_back(i);
  }
  int ans = 0, ansk;
  for (auto i : ordem) {
    for (j = 0; j < m[i].size(); j++) {
      pos = m[i][j];
      if (pos && v[pos - 1] <= i)
        join(pos, pos - 1);
      else if (pos < n - 1 && v[pos + 1] < i)
        join(pos, pos + 1);
      else
        add(1);
    }
    if (s.size() == 1 && (*s.begin()).second > ans)
      ans = (*s.begin()).second, ansk = i + 1;
  }
  printf("%d\n", ansk);
}
