#include <bits/stdc++.h>
using namespace std;
pair<int, int> P[100005];
int n, N[100005], grId[100005], GRId[100005],
    grInd = 1, GRInd = 1, grSum[100005], grNum[100005], resNum = -1, resK = -1;
void add(int ind, int i) {
  if (grId[ind - 1] != 0) {
    grId[ind] = grId[ind - 1];
    grNum[grSum[GRId[grId[ind]]]]--;
    grSum[GRId[grId[ind]]]++;
    grNum[grSum[GRId[grId[ind]]]]++;
  }
  if (grId[ind + 1] != 0) {
    if (grId[ind] == 0) {
      grId[ind] = grId[ind + 1];
      grNum[grSum[GRId[grId[ind]]]]--;
      grSum[GRId[grId[ind]]]++;
      grNum[grSum[GRId[grId[ind]]]]++;
    } else {
      grNum[grSum[GRId[grId[ind]]]]--;
      grNum[grSum[GRId[grId[ind + 1]]]]--;
      grSum[GRId[grId[ind]]] += grSum[GRId[grId[ind + 1]]];
      grSum[GRId[grId[ind + 1]]] = 0;
      GRId[grId[ind + 1]] = GRId[grId[ind]];
      grNum[grSum[GRId[grId[ind]]]]++;
    }
  }
  if (grId[ind - 1] == 0 && grId[ind + 1] == 0) {
    grId[ind] = grInd;
    GRId[grInd] = GRInd;
    grSum[GRInd]++;
    grNum[grSum[GRId[grId[ind]]]]++;
    grInd++;
    GRInd++;
  }
  int sum = grSum[GRId[grId[ind]]];
  int num = grNum[sum];
  if (num * sum == i) {
    if (resNum < num) {
      resNum = num;
      resK = N[ind] + 1;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> N[i];
    P[i].first = N[i];
    P[i].second = i;
  }
  sort(P, P + n + 1);
  for (int i = 1; i <= n; i++) {
    add(P[i].second, i);
  }
  cout << resK << endl;
  return 0;
}
