Problem: Takahashi loves sorting.

He has a permutation (p_1,p_2,...,p_N) of the integers from 1 through N. Now, he will repeat the following operation until the permutation becomes (1,2,...,N):

* First, we will define high and low elements in the permutation, as follows. The i-th element in the permutation is high if the maximum element between the 1-st and i-th elements, inclusive, is the i-th element itself, and otherwise the i-th element is low.
* Then, let a_1,a_2,...,a_k be the values of the high elements, and b_1,b_2,...,b_{N-k} be the values of the low elements in the current permutation, in the order they appear in it.
* Lastly, rearrange the permutation into (b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k).



How many operations are necessary until the permutation is sorted?

Constraints

* 1 ≤ N ≤ 2×10^5
* (p_1,p_2,...,p_N) is a permutation of the integers from 1 through N.

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

Print the number of operations that are necessary until the permutation is sorted.

Examples

Input

5
3 5 1 2 4


Output

3


Input

5
5 4 3 2 1


Output

4


Input

10
2 10 5 7 3 6 4 9 8 1


Output

6

Solution (in CPP):

Solution:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

#include <unistd.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> query;
typedef vector<vector<ll>> matrix;

int getTrueValue(int x) {
 return x != -1;
}

bool antoniosort1(int a, int b) {
  return getTrueValue(a) < getTrueValue(b);
}
bool antoniosort2(int a, int b) {
  return getTrueValue(a) > getTrueValue(b);
}

int slow(vector<int> v) {
  int ret = 0;
  int n = v.size();
  while(true) {
    while(v.size() && v.back() == n) {
      v.pop_back();
      n--;
    }
    if(n==0) break;
    int numMoves = 0;
    int last = -1;

    vector<int> w;
    w.resize(n);
    fill(w.begin(), w.end(), ~0);

    // print(v, w);
    for(int i = 0; i < n; i++) {
      if(v[i] > last) {

        // print before
        last = v[i];
        swap(v[i], w[i]);
      }
    }

    // print(v, w);

    stable_sort(v.begin(), v.end(), antoniosort2);
    stable_sort(w.begin(), w.end(), antoniosort1);

    // print(v, w);

    for(int i = 0; i < n; i++) {
      if(w[i] != -1) {
        numMoves++;
        swap(v[i], w[i]);
      }
    }

    if(numMoves == n) break;
    ret++;
  }
  return ret;
}

pii l[300000];

int a, b, nn;
vector<pii> validIntervals;

void f(int& ret, int idx) {
  bool check = false;
  for(auto out: validIntervals) {
    check |= out.first <= idx && idx <= out.second;
  }
  if(check) ret++;
  validIntervals.clear();
  if(a > b) swap(a, b);
  // a b idx
  if(idx > a && idx > b) {
    validIntervals.emplace_back(idx, 1 << 25);
    validIntervals.emplace_back(0, b);
    a = b;
    b = idx;
    return;
  }
  // idx a b
  if(idx < a && idx < b) {
    validIntervals.emplace_back(idx, b);
    a = idx;
    return;
  }
  // a idx b
  assert(a < idx && idx < b);
  validIntervals.emplace_back(idx, 1 << 25);
  validIntervals.emplace_back(0, a);
  b = idx;
}

int fast() {
  sort(l, l+nn);
  reverse(l, l+nn);
  validIntervals.clear();
  int ret = 0;
  if(l[1].second > l[0].second) {
    // 3 2
    ret++;
    validIntervals.emplace_back(l[1].second, 1 << 25);
    validIntervals.emplace_back(-1, l[0].second);
  }
  else {
    // 2 3
    validIntervals.emplace_back(l[1].second, 1 << 25);
  }
  a = l[0].second;
  b = l[1].second;
  for(int i = 2; i < nn; i++) {
    f(ret, l[i].second);
    /*
    for(pii out: validIntervals) {
      cout << out.first << " " << out.second << endl;
    }
    cout << endl;
    */
  }
  return ret;
}

void solve() {
  cin >> nn;
  if(nn == 1) {
    cout << "0\n";
    return;
  }
  for(int i = 0; i < nn; i++) {
    int t;
    cin >> t;
    l[i] = {t, i};
  }
  l[nn] = {nn+1, nn};
  nn++;
  cout << fast() << "\n";
}

void casesolve() {
  int t;
  cin >> t; cin.ignore();
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}

void debug() {
  int k = 4;
  vector<int> v;
  for(int i = 1; i <= k; i++) v.push_back(i);
  nn = k;
  do {
    for(int i = 0; i < k; i++) {
      l[i] = {v[i], i};
    }
    int ff = fast();
    int ss = slow(v);
    if(ff != ss) {
      cout << ff << " " << ss << endl;
      for(int out: v) cout << out; cout << endl;
      exit(0);
    }
  }
  while(next_permutation(v.begin(), v.end()));
}

int main() {
  // debug();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}