#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e5 + 5;
int n;
int a[Maxn];
int sz[Maxn];
int pa[Maxn];
pair<int, int> b[Maxn];
class root {
 public:
  int x;
  bool operator<(const root& o) const {
    return (sz[x] < sz[o.x]) || (sz[x] == sz[o.x] && x < o.x);
  }
  bool operator==(const root& o) const { return x == o.x; }
};
set<root> ss;
int find(int x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= n; i++) b[i] = pair<int, int>(a[i], i);
  sort(b + 1, b + n + 1);
  int cnt = 0, last = 0, ans;
  for (int i = 1; i <= n; i++) {
    int pos = b[i].second, val = b[i].first;
    sz[pos] = 1;
    pa[pos] = pos;
    if (find(pos + 1)) {
      pa[pos + 1] = pos;
      sz[pos] += sz[pos + 1];
      ss.erase(ss.lower_bound(root{pos + 1}));
      cnt--;
    }
    if (find(pos - 1)) {
      ss.erase(ss.lower_bound(root{pa[pos - 1]}));
      pa[pos] = pa[pos - 1];
      sz[pa[pos - 1]] += sz[pos];
      ss.insert(root{pa[pos - 1]});
    } else {
      ss.insert(root{pos});
      cnt++;
    }
    if (sz[ss.begin()->x] == sz[ss.rbegin()->x] && cnt > last) {
      last = cnt;
      ans = val + 1;
    }
  }
  printf("%d\n", ans);
  return 0;
}
