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 <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 2e6;
int n, a[nsz + 5], rt, lst, ans;
int ql, qr, q[nsz + 5];

struct treap {
	int sz, ls[nsz + 5], rs[nsz + 5], pri[nsz + 5];
	int key[nsz + 5], mn[nsz + 5], mx[nsz + 5];
	
	int inline node(int w) {
		int u = ++sz;
		key[u] = mn[u] = mx[u] = w, pri[u] = rand();
		return u;
	}
	
	void inline up(int u) {
		mn[u] = ls[u] ? mn[ls[u]] : key[u];
		mx[u] = rs[u] ? mx[rs[u]] : key[u];
	}
	
	int merge(int v1, int v2) {
		if (!v1 || !v2)  return v1 | v2;
		if (pri[v1] < pri[v2]) {
			rs[v1] = merge(rs[v1], v2), up(v1);
			return v1;
		} else {
			ls[v2] = merge(v1, ls[v2]), up(v2);
			return v2;
		}
	}
	
	void split(int u, int w, int &v1, int &v2) {
		if (!u) { v1 = v2 = 0; return; }
		if (key[u] <= w) {
			v1 = u, split(rs[u], w, rs[u], v2), up(u);
		} else {
			v2 = u, split(ls[u], w, v1, ls[u]), up(u);
		}
	}
	
	void inline ins(int &rt, int w) {
		rt = merge(rt, node(w));
	}
	
	void inline del(int &rt, int w) {
		int v1, v2;
		split(rt, w - 1, v1, v2);
		rt = v1;
	}
};
treap tr;

int inline pre(int id) { return id == 0 ? nsz : id - 1; }

int inline nxt(int id) { return id == nsz ? 0 : id + 1; }

void inline init() {
	cont (i, n - 1) {
		tr.ins(q[qr], a[i]);
		if (i != n && a[i] > a[i + 1])  qr = nxt(qr);
	}
	tr.ins(q[qr], a[n]);
	
	lst = n;
	for (; tr.mx[q[qr]] == lst && lst; --lst) {
		tr.del(q[qr], lst);
	}
	
	qr = nxt(qr);
}

void inline deal() {
	for (; !q[ql] && ql != qr; ql = nxt(ql));
	int u = q[ql], mx = tr.mx[u];
	q[ql] = 0, ql = nxt(ql);
	for (int k = ql; k != qr && mx != lst; k = nxt(k)) {
		if (!q[k])  continue;
		int v1, v2;
		tr.split(q[k], mx, v1, v2);
		q[k] = v1;
		u = tr.merge(u, v2);
		mx = max(mx, tr.mx[u]);
		
		int i = q[pre(k)], j = q[k];
		if (i && tr.mx[i] < tr.mn[j]) {
			q[k] = tr.merge(q[pre(k)], q[k]);
			q[pre(k)] = 0;
		}
	}
	q[qr] = u;
	int i = q[pre(qr)], j = q[qr];
	if (i && tr.mx[i] < tr.mn[j]) {
		q[qr] = tr.merge(q[pre(qr)], q[qr]);
		q[pre(qr)] = 0;
	}
	
	for (; tr.mx[q[qr]] == lst && lst; --lst) {
		tr.del(q[qr], lst);
	}
	
	qr = nxt(qr);
	++ans;
}

int main() {
	scanf("%d", &n);
	cont (i, n) {
		scanf("%d", &a[i]);
	}
	init();
	for (; lst; deal());
	printf("%d\n", ans);
}