#include <bits/stdc++.h>
using namespace std;
const string end_mark("^__=end=__^");
int naive(istream& cin, ostream& cout);
int body(istream& cin, ostream& cout);
void cmpNaive() {
  while (true) {
    string s;
    getline(cin, s);
    bool run_body;
    if (s.at(0) == 'Q') {
      return;
    } else if (s.at(0) == 'B') {
      run_body = true;
    } else if (s.at(0) == 'N') {
      run_body = false;
    } else {
      cerr << "Unknown body/naive specifier.\n";
      exit(1);
    }
    string input_s;
    while (true) {
      getline(cin, s);
      if (s == end_mark) break;
      input_s += s;
      input_s += "\n";
    }
    stringstream ss_in(move(input_s));
    stringstream ss_out;
    if (run_body) {
      body(ss_in, ss_out);
    } else {
      naive(ss_in, ss_out);
    }
    cout << ss_out.str() << end_mark << endl;
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);
  body(cin, cout);
  return 0;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
  os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
  return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
  os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", "
     << get<3>(t) << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << '[';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << ']';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const set<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const unordered_set<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const multiset<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T1, typename T2, typename C>
ostream& operator<<(ostream& os, const map<T1, T2, C>& mp) {
  os << '[';
  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it != mp.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  os << ']';
  return os;
}
template <typename T1, typename T2, typename C>
ostream& operator<<(ostream& os, const unordered_map<T1, T2, C>& mp) {
  os << '[';
  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it != mp.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  os << ']';
  return os;
}
template <typename T, typename T2>
ostream& operator<<(ostream& os, const queue<T, T2>& orig) {
  queue<T, T2> que(orig);
  bool first = true;
  os << '[';
  while (!que.empty()) {
    T x = que.front();
    que.pop();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T, typename T2>
ostream& operator<<(ostream& os, const deque<T, T2>& orig) {
  deque<T, T2> que(orig);
  bool first = true;
  os << '[';
  while (!que.empty()) {
    T x = que.front();
    que.pop_front();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T, typename T2, typename T3>
ostream& operator<<(ostream& os, const priority_queue<T, T2, T3>& orig) {
  priority_queue<T, T2, T3> pq(orig);
  bool first = true;
  os << '[';
  while (!pq.empty()) {
    T x = pq.top();
    pq.pop();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T>
ostream& operator<<(ostream& os, const stack<T>& st) {
  stack<T> tmp(st);
  os << '[';
  bool first = true;
  while (!tmp.empty()) {
    T& t = tmp.top();
    if (first)
      first = false;
    else
      os << ", ";
    os << t;
    tmp.pop();
  }
  os << ']';
  return os;
}
ostream& operator<<(ostream& os, int8_t x) {
  os << (int32_t)x;
  return os;
}
template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}
template <class Head>
void dbgLog(bool with_nl, Head&& head) {
  cerr << head;
  if (with_nl) cerr << endl;
}
template <class Head, class... Tail>
void dbgLog(bool with_nl, Head&& head, Tail&&... tail) {
  cerr << head << " ";
  dbgLog(with_nl, forward<Tail>(tail)...);
}
int naive(istream& cin, ostream& cout) {
  long long int n;
  cin >> n;
  vector<long long int> A(n);
  long long int maxA = LLONG_MIN;
  long long int minA = LLONG_MAX;
  for (long long int i = 0; i < n; i++) {
    long long int a;
    cin >> a;
    A[i] = a;
    maxA = max(maxA, a);
    minA = min(minA, a);
  }
  long long int numLoc = 0;
  long long int ans = -1;
  for (long long int k = minA + 1; k <= maxA; k++) {
    long long int cnt = 0;
    long long int start = -1;
    long long int len = -1;
    bool succ = true;
    for (long long int i = 0; i <= n; i++) {
      if (i == n || A[i] >= k) {
        if (i - 1 >= 0 && A[i - 1] < k) {
          long long int l = i - start;
          if (len < 0)
            len = l;
          else if (len != l) {
            succ = false;
            break;
          }
        }
      } else if (i == 0 || A[i - 1] >= k) {
        start = i;
        cnt += 1;
      }
    }
    if (!succ) continue;
    if (numLoc < cnt) {
      numLoc = cnt;
      ans = k;
    }
  }
  cout << ans << endl;
  return 0;
}
int body(istream& cin, ostream& cout) {
  long long int n;
  cin >> n;
  vector<long long int> A(n);
  for (long long int i = 0; i < n; i++) cin >> A[i];
  auto C(A);
  sort(C.begin(), C.end());
  map<long long int, long long int> c_mp;
  for (long long int i = 0; i < n; i++) c_mp[C[i]] = i;
  vector<long long int> yx(n);
  for (long long int i = 0; i < n; i++) yx[c_mp[A[i]]] = i;
  using info_t = tuple<long long int, long long int, long long int>;
  set<long long int> used;
  used.insert(-1);
  used.insert(n);
  vector<info_t> eInfo(n), bInfo(n);
  set<info_t> szset;
  long long int max_seg = 0;
  long long int ans = -1;
  for (long long int i = 0; i < n; i++) {
    long long int j = yx[i];
    auto it = used.upper_bound(j);
    long long int b2 = *it;
    it--;
    long long int e1 = *it;
    if (b2 < n && j + 1 == b2 && e1 >= 0 && e1 + 1 == j) {
      info_t p2 = bInfo[b2];
      info_t p1 = eInfo[e1];
      auto [sz2, bb2, ee2] = p2;
      auto [sz1, bb1, ee1] = p1;
      szset.erase(p2);
      szset.erase(p1);
      info_t newp(sz1 + sz2 + 1, bb1, ee2);
      szset.insert(newp);
      bInfo[bb1] = newp;
      eInfo[ee2] = newp;
    } else if (b2 < n && j + 1 == b2) {
      info_t p = bInfo[b2];
      auto [sz, bb, ee] = p;
      szset.erase(p);
      info_t newp(sz + 1, j, ee);
      szset.insert(newp);
      bInfo[j] = newp;
      eInfo[ee] = newp;
    } else if (e1 >= 0 && e1 + 1 == j) {
      info_t p = eInfo[e1];
      auto [sz, bb, ee] = p;
      szset.erase(p);
      info_t newp(sz + 1, bb, j);
      szset.insert(newp);
      bInfo[bb] = newp;
      eInfo[j] = newp;
    } else {
      info_t newp(1, j, j);
      szset.insert(newp);
      bInfo[j] = newp;
      eInfo[j] = newp;
    }
    used.insert(j);
    ;
    ;
    ;
    ;
    auto [sz1, d1, d2] = *szset.begin();
    auto sit = szset.end();
    sit--;
    auto [sz2, d3, d4] = *sit;
    if (sz1 == sz2) {
      if (max_seg < (long long int)szset.size()) {
        max_seg = szset.size();
        ans = C[i] + 1;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve 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>
using namespace std;
const string end_mark("^__=end=__^");
int naive(istream& cin, ostream& cout);
int body(istream& cin, ostream& cout);
void cmpNaive() {
  while (true) {
    string s;
    getline(cin, s);
    bool run_body;
    if (s.at(0) == 'Q') {
      return;
    } else if (s.at(0) == 'B') {
      run_body = true;
    } else if (s.at(0) == 'N') {
      run_body = false;
    } else {
      cerr << "Unknown body/naive specifier.\n";
      exit(1);
    }
    string input_s;
    while (true) {
      getline(cin, s);
      if (s == end_mark) break;
      input_s += s;
      input_s += "\n";
    }
    stringstream ss_in(move(input_s));
    stringstream ss_out;
    if (run_body) {
      body(ss_in, ss_out);
    } else {
      naive(ss_in, ss_out);
    }
    cout << ss_out.str() << end_mark << endl;
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);
  body(cin, cout);
  return 0;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
  os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
  return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
  os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", "
     << get<3>(t) << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << '[';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << ']';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const set<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const unordered_set<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const multiset<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T1, typename T2, typename C>
ostream& operator<<(ostream& os, const map<T1, T2, C>& mp) {
  os << '[';
  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it != mp.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  os << ']';
  return os;
}
template <typename T1, typename T2, typename C>
ostream& operator<<(ostream& os, const unordered_map<T1, T2, C>& mp) {
  os << '[';
  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it != mp.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  os << ']';
  return os;
}
template <typename T, typename T2>
ostream& operator<<(ostream& os, const queue<T, T2>& orig) {
  queue<T, T2> que(orig);
  bool first = true;
  os << '[';
  while (!que.empty()) {
    T x = que.front();
    que.pop();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T, typename T2>
ostream& operator<<(ostream& os, const deque<T, T2>& orig) {
  deque<T, T2> que(orig);
  bool first = true;
  os << '[';
  while (!que.empty()) {
    T x = que.front();
    que.pop_front();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T, typename T2, typename T3>
ostream& operator<<(ostream& os, const priority_queue<T, T2, T3>& orig) {
  priority_queue<T, T2, T3> pq(orig);
  bool first = true;
  os << '[';
  while (!pq.empty()) {
    T x = pq.top();
    pq.pop();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T>
ostream& operator<<(ostream& os, const stack<T>& st) {
  stack<T> tmp(st);
  os << '[';
  bool first = true;
  while (!tmp.empty()) {
    T& t = tmp.top();
    if (first)
      first = false;
    else
      os << ", ";
    os << t;
    tmp.pop();
  }
  os << ']';
  return os;
}
ostream& operator<<(ostream& os, int8_t x) {
  os << (int32_t)x;
  return os;
}
template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}
template <class Head>
void dbgLog(bool with_nl, Head&& head) {
  cerr << head;
  if (with_nl) cerr << endl;
}
template <class Head, class... Tail>
void dbgLog(bool with_nl, Head&& head, Tail&&... tail) {
  cerr << head << " ";
  dbgLog(with_nl, forward<Tail>(tail)...);
}
int naive(istream& cin, ostream& cout) {
  long long int n;
  cin >> n;
  vector<long long int> A(n);
  long long int maxA = LLONG_MIN;
  long long int minA = LLONG_MAX;
  for (long long int i = 0; i < n; i++) {
    long long int a;
    cin >> a;
    A[i] = a;
    maxA = max(maxA, a);
    minA = min(minA, a);
  }
  long long int numLoc = 0;
  long long int ans = -1;
  for (long long int k = minA + 1; k <= maxA; k++) {
    long long int cnt = 0;
    long long int start = -1;
    long long int len = -1;
    bool succ = true;
    for (long long int i = 0; i <= n; i++) {
      if (i == n || A[i] >= k) {
        if (i - 1 >= 0 && A[i - 1] < k) {
          long long int l = i - start;
          if (len < 0)
            len = l;
          else if (len != l) {
            succ = false;
            break;
          }
        }
      } else if (i == 0 || A[i - 1] >= k) {
        start = i;
        cnt += 1;
      }
    }
    if (!succ) continue;
    if (numLoc < cnt) {
      numLoc = cnt;
      ans = k;
    }
  }
  cout << ans << endl;
  return 0;
}
int body(istream& cin, ostream& cout) {
  long long int n;
  cin >> n;
  vector<long long int> A(n);
  for (long long int i = 0; i < n; i++) cin >> A[i];
  auto C(A);
  sort(C.begin(), C.end());
  map<long long int, long long int> c_mp;
  for (long long int i = 0; i < n; i++) c_mp[C[i]] = i;
  vector<long long int> yx(n);
  for (long long int i = 0; i < n; i++) yx[c_mp[A[i]]] = i;
  using info_t = tuple<long long int, long long int, long long int>;
  set<long long int> used;
  used.insert(-1);
  used.insert(n);
  vector<info_t> eInfo(n), bInfo(n);
  set<info_t> szset;
  long long int max_seg = 0;
  long long int ans = -1;
  for (long long int i = 0; i < n; i++) {
    long long int j = yx[i];
    auto it = used.upper_bound(j);
    long long int b2 = *it;
    it--;
    long long int e1 = *it;
    if (b2 < n && j + 1 == b2 && e1 >= 0 && e1 + 1 == j) {
      info_t p2 = bInfo[b2];
      info_t p1 = eInfo[e1];
      auto [sz2, bb2, ee2] = p2;
      auto [sz1, bb1, ee1] = p1;
      szset.erase(p2);
      szset.erase(p1);
      info_t newp(sz1 + sz2 + 1, bb1, ee2);
      szset.insert(newp);
      bInfo[bb1] = newp;
      eInfo[ee2] = newp;
    } else if (b2 < n && j + 1 == b2) {
      info_t p = bInfo[b2];
      auto [sz, bb, ee] = p;
      szset.erase(p);
      info_t newp(sz + 1, j, ee);
      szset.insert(newp);
      bInfo[j] = newp;
      eInfo[ee] = newp;
    } else if (e1 >= 0 && e1 + 1 == j) {
      info_t p = eInfo[e1];
      auto [sz, bb, ee] = p;
      szset.erase(p);
      info_t newp(sz + 1, bb, j);
      szset.insert(newp);
      bInfo[bb] = newp;
      eInfo[j] = newp;
    } else {
      info_t newp(1, j, j);
      szset.insert(newp);
      bInfo[j] = newp;
      eInfo[j] = newp;
    }
    used.insert(j);
    ;
    ;
    ;
    ;
    auto [sz1, d1, d2] = *szset.begin();
    auto sit = szset.end();
    sit--;
    auto [sz2, d3, d4] = *sit;
    if (sz1 == sz2) {
      if (max_seg < (long long int)szset.size()) {
        max_seg = szset.size();
        ans = C[i] + 1;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

```