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 = 2e5;
int n, a[nsz + 5], rt, lst, ans;
int ql, qr, q[2 * 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;
		return pri[v1] < pri[v2] ? (rs[v1] = merge(rs[v1], v2), up(v1), v1) : (ls[v2] = merge(v1, ls[v2]), up(v2), v2);
	}
	
	void split(int u, int w, int &v1, int &v2) {
		if (!u) { v1 = v2 = 0; return; }
		key[u] <= w ? (v1 = u, split(rs[u], w, rs[u], v2), up(u)) : (v2 = u, split(ls[u], w, v1, ls[u]), up(u));
	}
	
	void inline push_back(int &rt, int w) { rt = merge(rt, node(w)); }
	
	void inline pop_back(int &rt, int w) { int v; split(rt, w - 1, rt, v); }
};
treap tr;

void inline init() {
	cont (i, n) {
		if (i == 1 || a[i] < a[i - 1])  ++qr;
		tr.push_back(q[qr - 1], a[i]);
	}
	
	for (lst = n; tr.mx[q[qr - 1]] == lst && lst; tr.pop_back(q[qr - 1], lst--));
}

void inline deal() {
	for (++ans; !q[ql] && ql != qr; ++ql);
	
	int u = q[ql++], mx = tr.mx[u], v1, v2;
	for (int k = ql; k != qr && mx != lst; ++k) {
		if (!q[k] || tr.mx[q[k]] < mx)  continue;
		
		tr.split(q[k], mx, v1, v2);
		q[k] = v1, u = tr.merge(u, v2), mx = tr.mx[u];
		
		int &r1 = q[k - 1], &r2 = q[k];
		if (r1 && tr.mx[r1] < tr.mn[r2])  r2 = tr.merge(r1, r2), r1 = 0;
	}
	
	int &r1 = q[qr - 1], &r2 = u;
	if (r1 && tr.mx[r1] < tr.mn[r2])  r2 = tr.merge(r1, r2), r1 = 0;
	for (; tr.mx[u] == lst && lst; tr.pop_back(u, lst--));
	
	q[qr++] = u;
}

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