#include <bits/stdc++.h>
using namespace std;
const long long N = 100100;
long long n;
long long a[N];
long long p[N];
long long w[N];
bool taken[N];
map<long long, vector<long long>> mp;
set<long long> values;
multiset<long long> st;
long long f(long long x) { return x == p[x] ? x : p[x] = f(p[x]); }
void un(long long x, long long y) {
  assert((x = f(x)) != (y = f(y)));
  st.erase(st.find(w[x]));
  st.erase(st.find(w[y]));
  w[x] += w[y];
  st.insert(w[x]);
  p[y] = x;
}
void man_self(pair<long long, long long>& p1, pair<long long, long long> p2) {
  if (p2.first > p1.first || (p2.first == p1.first && p2.second < p1.second))
    p1 = p2;
}
int main() {
  for (long long i = 0; i < N; i++) p[i] = i, w[i] = 1;
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    scanf("%I64d", a + i);
    values.insert(a[i]);
    mp[a[i]].push_back(i);
  }
  pair<long long, long long> Ans = pair<long long, long long>(0, 1);
  for (auto x : values) {
    for (auto y : mp[x]) {
      taken[y] = true;
      st.insert(w[y]);
      for (long long z : {y - 1, y + 1})
        if (taken[z]) un(y, z);
    }
    if ((*st.begin()) == (*st.rbegin()))
      man_self(Ans, pair<long long, long long>(st.size(), x + 1));
  }
  cout << Ans.second;
}
