#include <bits/stdc++.h>
using namespace std;
class segment_tree {
 public:
  explicit segment_tree(int _size) { root = new Node(0, _size - 1); }
  void set_value(int tl, int tr, int val) { update(root, tl, tr, val); }
  int get_item(int id) const { return get_value(root, id); }

 private:
  struct Node {
    int l, r;
    int val, to_push;
    Node *left, *right;
    Node(int tl, int tr) : l(tl), r(tr) {
      if (l == r) {
        val = -1;
        to_push = -1;
      } else {
        int mid = (l + r) >> 1;
        left = new Node(l, mid);
        right = new Node(mid + 1, r);
        val = -1;
        to_push = -1;
      }
    }
    inline void push() {
      if (to_push == -1) {
        return;
      }
      if (l != r) {
        left->val = to_push;
        right->val = to_push;
        left->to_push = to_push;
        right->to_push = to_push;
      }
      to_push = -1;
    }
  };
  Node *root;
  void update(Node *vrt, int tl, int tr, int val) {
    vrt->push();
    if (tl > tr) {
      return;
    }
    if (tl == vrt->l && tr == vrt->r) {
      vrt->val = val;
      vrt->to_push = val;
    } else {
      int mid = (vrt->l + vrt->r) >> 1;
      update(vrt->left, tl, min(mid, tr), val);
      update(vrt->right, max(mid + 1, tl), tr, val);
    }
  }
  int get_value(Node *vrt, int id) const {
    vrt->push();
    if (vrt->l == vrt->r) {
      return vrt->val;
    } else {
      int mid = (vrt->l + vrt->r) >> 1;
      if (id <= mid) {
        return get_value(vrt->left, id);
      } else {
        return get_value(vrt->right, id);
      }
    }
  }
};
struct node {
  int l, r;
};
segment_tree *tree;
map<int, int> _sizes;
vector<node> reg;
void update(int pos) {
  int left_pos = tree->get_item(pos - 1);
  int right_pos = tree->get_item(pos + 1);
  if (left_pos != -1 && right_pos == -1) {
    int cur_sz = reg[left_pos].r - reg[left_pos].l + 1;
    --_sizes[cur_sz];
    if (_sizes[cur_sz] == 0) {
      _sizes.erase(_sizes.find(cur_sz));
    }
    ++reg[left_pos].r;
    ++cur_sz;
    ++_sizes[cur_sz];
    tree->set_value(pos, pos, left_pos);
    return;
  }
  if (left_pos == -1 && right_pos != -1) {
    int cur_sz = reg[right_pos].r - reg[right_pos].l + 1;
    --_sizes[cur_sz];
    if (_sizes[cur_sz] == 0) {
      _sizes.erase(_sizes.find(cur_sz));
    }
    --reg[right_pos].l;
    ++_sizes[cur_sz + 1];
    tree->set_value(pos, pos, right_pos);
    return;
  }
  if (left_pos == -1 && right_pos == -1) {
    reg.push_back({pos, pos});
    tree->set_value(pos, pos, reg.size() - 1);
    ++_sizes[1];
    return;
  }
  if (left_pos != -1 && right_pos != -1) {
    int lcur_sz = reg[left_pos].r - reg[left_pos].l + 1;
    --_sizes[lcur_sz];
    if (_sizes[lcur_sz] == 0) {
      _sizes.erase(_sizes.find(lcur_sz));
    }
    int rcur_sz = reg[right_pos].r - reg[right_pos].l + 1;
    --_sizes[rcur_sz];
    if (_sizes[rcur_sz] == 0) {
      _sizes.erase(_sizes.find(rcur_sz));
    }
    reg[left_pos].r = reg[right_pos].r;
    int cur_sz = lcur_sz + rcur_sz + 1;
    tree->set_value(reg[left_pos].l, reg[left_pos].r, left_pos);
    ++_sizes[cur_sz];
    return;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  map<int, vector<int>> nums;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int a;
    cin >> a;
    nums[a].push_back(i);
  }
  tree = new segment_tree(n + 3);
  int ans = -1, count = 0;
  for (auto nw = nums.begin(); nw != nums.end(); ++nw) {
    for (int i = 0; i < nw->second.size(); ++i) {
      update(nw->second[i]);
    }
    if (_sizes.size() == 1) {
      if (_sizes.begin()->second > count) {
        ans = nw->first + 1;
        count = _sizes.begin()->second;
      }
    }
  }
  cout << ans;
  return 0;
}
