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 <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)

const int maxn = 2e5 + 5;
int mx[maxn];
int n, a[maxn];

void upd(int x, int v) {
	for (; x < maxn; x += x & -x) mx[x] = max(mx[x], v);
}

int qry(int x) {
	int ans = 0;
	for (; x; x -= x & -x) ans = max(ans, mx[x]);
	return ans;
}

struct T {
	int val, fix;
	T *ls, *rs;
	T(int v) {val = v, fix = rand(), ls = rs = NULL;}
};

void split(T *x, int v, T *&a, T *&b) {
	if (!x) {a = b = NULL; return ;}
	if (x->val <= v) a = x, split(x->rs, v, a->rs, b);
	else b = x, split(x->ls, v, a, b->ls);
}

T *merge(T *a, T *b) {
	if (!a || !b) return a ? a : b;
	if (a->fix < b->fix) {a->rs = merge(a->rs, b); return a;}
	else {b->ls = merge(a, b->ls); return b;}
}

int mxv(T *x) {while (x && x->rs) x = x->rs; return x ? x->val : 0;}
void prt(T *x) {if (x) prt(x->ls), printf("%d ", x->val), prt(x->rs);}

T *rt[maxn * 2];
vector <int> lst;
int f[maxn];

int main() {
//	freopen("in", "r", stdin);
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
	for (int i = 0; i < n; ++ i) {
		int v = qry(n - a[i] + 1);
		rt[v] = merge(rt[v], new T(a[i]));
		f[a[i]] = v;
		upd(n - a[i] + 1, v + 1);
	}
	lst.resize(qry(n));
	for (int i = 0; i < lst.size(); ++ i) lst[i] = mxv(rt[i]);
	for (int i = 0; i < lst.size() - 1; ++ i) {
		while (rt[i]) {
			int x = mxv(rt[i]);
			int lb = i + 1, rb = lst.size();
			while (lb < rb) {
				int md = (lb + rb) >> 1;
				if (lst[md] > x) lb = md + 1;
				else rb = md;
			}
			if (lb == lst.size()) lst.pb(0);
			T *a, *b;
			split(rt[i], lst[lb], a, b);
			rt[i] = a; rt[lb] = merge(rt[lb], b);
			lst[i] = mxv(a); lst[lb] = mxv(rt[lb]);
		}
	}
	printf("%d\n", int(lst.size()) - 1);
//	printf("%.3f\n", clock() * 1.0 / CLOCKS_PER_SEC);
	return 0;
}