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;

namespace io {
	#define isdigit(c)  (c >= '0' && c <= '9')
	#define getchar()   (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
	#define flush()     (fwrite(puf, 1, pp - puf, stdout), pp = puf)
	#define putchar(c)  (*pp++ = c, pp - puf == bufsz && flush())
	
	const int bufsz = 1 << 22;
	static char buf[bufsz], puf[bufsz], *p1, *p2, *pp = puf;
	struct flusher { ~flusher() { flush(); } } flusher;
	
	void inline read(int &a) {
		int c = getchar();
		for (; !isdigit(c); c = getchar());
		for (a = 0; isdigit(c); a *= 10, a += c & 15, c = getchar());
	}
	
	void inline write(int a, char c = ln) {
		static char d[20];
		int s = d[0] = 0;
		for (; a; d[s++] = a % 10, a /= 10);
		for (s || (s = 1); s; putchar(d[--s] + 48));
		putchar(c);
	}
}
using namespace io;

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

int sz, ls[nsz + 5], rs[nsz + 5], pri[nsz + 5], key[nsz + 5];

int inline node(int w) {
	int u = ++sz;
	key[u] = w, pri[u] = rand();
	return u;
}

int merge(int v1, int v2) {
	if (!v1 || !v2)  return v1 | v2;
	return pri[v1] < pri[v2] ? (rs[v1] = merge(rs[v1], v2), v1) : (ls[v2] = merge(v1, ls[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)) : (v2 = u, split(ls[u], w, v1, ls[u]));
}

void inline push_back(int &rt, int w) { rt = merge(rt, node(w)); }

void inline pop_back(int &rt, int w) { split(rt, w - 1, rt, *new int); }

int inline mn(int u) {
	for (; ls[u]; u = ls[u]);
	return key[u];
}

int inline mx(int u) {
	for (; rs[u]; u = rs[u]);
	return key[u];
}

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

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

int main() {
	read(n);
	cont (i, n) {
		read(a[i]);
	}
	for (init(); lst; deal());
	write(ans);
}