#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int scan() { return getchar(); }
void scan(int& a) { cin >> a; }
void scan(long long& a) { cin >> a; }
void scan(char& a) { cin >> a; }
void scan(double& a) { cin >> a; }
void scan(long double& a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string& a) { cin >> a; }
template <class T>
void scan(vector<T>&);
template <class T, size_t size>
void scan(array<T, size>&);
template <class T, class L>
void scan(pair<T, L>&);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(deque<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size>& a) {
  for (auto& i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L>& p) {
  scan(p.first);
  scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(T& a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head& head, Tail&... tail) {
  scan(head);
  IN(tail...);
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
template <class T>
void UNIQUE(vector<T>& x) {
  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), x.end());
}
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  unsigned long long x;
  cin >> x;
  return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string& a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L>& p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T>
void print(set<T>& x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T>
void print(multiset<T>& x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T& a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T& t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
vector<pair<long long, long long>> factor(long long x) {
  vector<pair<long long, long long>> ans;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back({i, 1});
      while ((x /= i) % i == 0) ans.back().second++;
    }
  if (x != 1) ans.push_back({x, 1});
  return ans;
}
vector<int> divisor(int x) {
  vector<int> ans;
  for (int i = 1; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back(i);
      if (i * i != x) ans.push_back(x / i);
    }
  return ans;
}
int popcount(long long x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }
template <class... T>
void err(const T&...) {}
struct Setup_io {
  Setup_io() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
  }
} setup_io;
template <typename T>
struct edge {
  int from, to, id;
  T cost;
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
  edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost) {}
  edge& operator=(const int& x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedTree = vector<Edges<T>>;
using tree = vector<vector<int>>;
tree make(int n, int offset = 1) {
  tree res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    res[a].emplace_back(b);
    res[b].emplace_back(a);
  }
  return res;
}
template <typename T>
WeightedTree<T> make2(int n, int offset = 1) {
  WeightedTree<T> res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    T c;
    cin >> c;
    res[a].emplace_back(b, c);
    res[b].emplace_back(a, c);
  }
  return res;
}
signed main() {
  multiset<int> d;
  set<pair<int, int>> s;
  int n;
  IN(n);
  vector<int> a(n);
  IN(a);
  a.insert(a.begin(), INT_MAX);
  a.emplace_back(INT_MAX);
  auto id = iota(n + 2);
  sort(begin(id), end(id), [&](int x, int y) { return a[x] < a[y]; });
  vector<int> used(n + 2);
  int cnt = 0, ans = INT_MAX;
  for (long long j = 0; j < n + 2; ++j) {
    int i = id[j];
    if (a[i] == INT_MAX) break;
    if (used[i - 1] and used[i + 1]) {
      auto it = --s.lower_bound(pair<int, int>(i, 0));
      auto it2 = s.lower_bound(pair<int, int>(i, 0));
      int l = it->first;
      int r = it2->second;
      it = s.erase(it);
      s.erase(it);
      d.erase(d.lower_bound(i - l));
      d.erase(d.lower_bound(r - i));
      d.emplace(r - l + 1);
      s.emplace(l, r);
    } else if (used[i - 1]) {
      auto it = --s.lower_bound(pair<int, int>(i, 0));
      int l = it->first;
      s.erase(it);
      s.emplace(l, i);
      int dist = i - l + 1;
      d.erase(d.lower_bound(dist - 1));
      d.emplace(dist);
    } else if (used[i + 1]) {
      auto it = s.lower_bound(pair<int, int>(i, 0));
      int r = it->second;
      s.erase(it);
      s.emplace(i, r);
      d.erase(d.lower_bound(r - i));
      d.emplace(r - i + 1);
    } else {
      d.emplace(1);
      s.emplace(i, i);
    }
    used[i] = true;
    if (a[id[j + 1]] > a[id[j]] and *d.begin() == *(--d.end())) {
      if (cnt < d.size()) {
        cnt = d.size();
        ans = a[i] + 1;
      } else if (cnt == d.size()) {
        chmin(ans, a[i] + 1);
      }
    }
  }
  cout << ans << '\n';
}

### Prompt

Please create a solution in cpp to the following problem:

For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For n days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer k that if the shark in some day traveled the distance strictly less than k, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to k; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least k.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of n days we can find consecutive nonempty segments when the shark traveled the distance less than k in each of the days: each such segment corresponds to one location. Max wants to choose such k that the lengths of all such segments are equal.

Find such integer k, that the number of locations is as large as possible. If there are several such k, print the smallest one.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of days.

The second line contains n distinct positive integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — the distance traveled in each of the day.

Output

Print a single integer k, such that 

  1. the shark was in each location the same number of days, 
  2. the number of locations is maximum possible satisfying the first condition, 
  3. k is smallest possible satisfying the first and second conditions. 

Examples

Input

8
1 2 7 3 4 8 5 6


Output

7

Input

6
25 1 2 3 14 36


Output

2

Note

In the first example the shark travels inside a location on days 1 and 2 (first location), then on 4-th and 5-th days (second location), then on 7-th and 8-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the 2-nd day, so there is only one location.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int scan() { return getchar(); }
void scan(int& a) { cin >> a; }
void scan(long long& a) { cin >> a; }
void scan(char& a) { cin >> a; }
void scan(double& a) { cin >> a; }
void scan(long double& a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string& a) { cin >> a; }
template <class T>
void scan(vector<T>&);
template <class T, size_t size>
void scan(array<T, size>&);
template <class T, class L>
void scan(pair<T, L>&);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(deque<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size>& a) {
  for (auto& i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L>& p) {
  scan(p.first);
  scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(T& a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head& head, Tail&... tail) {
  scan(head);
  IN(tail...);
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
template <class T>
void UNIQUE(vector<T>& x) {
  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), x.end());
}
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  unsigned long long x;
  cin >> x;
  return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string& a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L>& p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T>
void print(set<T>& x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T>
void print(multiset<T>& x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T& a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T& t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
vector<pair<long long, long long>> factor(long long x) {
  vector<pair<long long, long long>> ans;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back({i, 1});
      while ((x /= i) % i == 0) ans.back().second++;
    }
  if (x != 1) ans.push_back({x, 1});
  return ans;
}
vector<int> divisor(int x) {
  vector<int> ans;
  for (int i = 1; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back(i);
      if (i * i != x) ans.push_back(x / i);
    }
  return ans;
}
int popcount(long long x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }
template <class... T>
void err(const T&...) {}
struct Setup_io {
  Setup_io() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
  }
} setup_io;
template <typename T>
struct edge {
  int from, to, id;
  T cost;
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
  edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost) {}
  edge& operator=(const int& x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedTree = vector<Edges<T>>;
using tree = vector<vector<int>>;
tree make(int n, int offset = 1) {
  tree res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    res[a].emplace_back(b);
    res[b].emplace_back(a);
  }
  return res;
}
template <typename T>
WeightedTree<T> make2(int n, int offset = 1) {
  WeightedTree<T> res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    T c;
    cin >> c;
    res[a].emplace_back(b, c);
    res[b].emplace_back(a, c);
  }
  return res;
}
signed main() {
  multiset<int> d;
  set<pair<int, int>> s;
  int n;
  IN(n);
  vector<int> a(n);
  IN(a);
  a.insert(a.begin(), INT_MAX);
  a.emplace_back(INT_MAX);
  auto id = iota(n + 2);
  sort(begin(id), end(id), [&](int x, int y) { return a[x] < a[y]; });
  vector<int> used(n + 2);
  int cnt = 0, ans = INT_MAX;
  for (long long j = 0; j < n + 2; ++j) {
    int i = id[j];
    if (a[i] == INT_MAX) break;
    if (used[i - 1] and used[i + 1]) {
      auto it = --s.lower_bound(pair<int, int>(i, 0));
      auto it2 = s.lower_bound(pair<int, int>(i, 0));
      int l = it->first;
      int r = it2->second;
      it = s.erase(it);
      s.erase(it);
      d.erase(d.lower_bound(i - l));
      d.erase(d.lower_bound(r - i));
      d.emplace(r - l + 1);
      s.emplace(l, r);
    } else if (used[i - 1]) {
      auto it = --s.lower_bound(pair<int, int>(i, 0));
      int l = it->first;
      s.erase(it);
      s.emplace(l, i);
      int dist = i - l + 1;
      d.erase(d.lower_bound(dist - 1));
      d.emplace(dist);
    } else if (used[i + 1]) {
      auto it = s.lower_bound(pair<int, int>(i, 0));
      int r = it->second;
      s.erase(it);
      s.emplace(i, r);
      d.erase(d.lower_bound(r - i));
      d.emplace(r - i + 1);
    } else {
      d.emplace(1);
      s.emplace(i, i);
    }
    used[i] = true;
    if (a[id[j + 1]] > a[id[j]] and *d.begin() == *(--d.end())) {
      if (cnt < d.size()) {
        cnt = d.size();
        ans = a[i] + 1;
      } else if (cnt == d.size()) {
        chmin(ans, a[i] + 1);
      }
    }
  }
  cout << ans << '\n';
}

```