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:
#pragma GCC optimize("Ofast")
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

int Max(int a, int b) {return a > b ? a : b;}

#define maxn 200005

struct T {
	char mon;
	int val, mx, fst;
	int fix;
	T *lson, *rson;
} t[maxn];

int tot;

T *new_node(int v) {
	T *x = &t[++ tot];
	x->mon = 1;
	x->val = v; x->mx = v; x->fst = v;
	x->fix = rand();
	x->lson = x->rson = 0;
	return x;
}

void pushup0(T *x) {
	x->fst = x->lson ? x->lson->fst : x->val;
	char mo = 1;
	x->mx = x->val;
	if (x->lson) {
		x->mx = Max(x->mx, x->lson->mx);
		mo &= x->lson->mon && x->lson->mx < x->val;
	}
	if (x->rson) {
		x->mx = Max(x->mx, x->rson->mx);
		mo &= x->rson->mon && x->val < x->rson->fst;
	}
	x->mon = mo;
}

void pushup1(T *x) {
	x->mon = 1;
	x->fst = x->lson ? x->lson->fst : x->val;
	x->mx = x->rson ? x->rson->mx : x->val;
}

T *merge0(T *a, T *b) {
	if (!a || !b) return a ? a : b;
	if (a->fix < b->fix) {
		a->rson = merge0(a->rson, b);
		pushup0(a);
		return a;
	} else {
		b->lson = merge0(a, b->lson);
		pushup0(b);
		return b;
	}
}

T *merge1(T *a, T *b) {
	if (!a || !b) return a ? a : b;
	if (a->fix < b->fix) {
		a->rson = merge1(a->rson, b);
		pushup1(a);
		return a;
	} else {
		b->lson = merge1(a, b->lson);
		pushup1(b);
		return b;
	}
}

int split(T *x, int v, T *&a, T *&b) {
	if (!x) {a = b = 0; return v;}
	if (x->mx < v) {a = x; b = 0; return v;}
	if (x->mon) {
		if (x->fst > v) {a = 0; b = x; return b->mx;}
		if (x->val < v) {
			a = x; split(x->rson, v, a->rson, b);
			pushup1(a); return b->mx;
		} else {
			b = x; split(x->lson, v, a, b->lson);
			pushup1(b); return b->mx;
		}
	} else {
		T *ls = x->lson, *rs = x->rson;
		x->lson = x->rson = 0;
		pushup1(x);
		v = split(ls, v, a, b);
		if (x->val > v) b = merge1(b, x), v = x->val;
		else a = merge0(a, x);
		T *c, *d;
		v = split(rs, v, c, d);
		a = merge0(a, c); b = merge1(b, d);
		return v;
	}
}

T *rt;

int main() {
//	freopen("in", "r", stdin);
	srand(200);
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) {
		int p; scanf("%d", &p);
		rt = merge0(rt, new_node(p));
	}
	int ans = 0;
	while (!rt->mon) {
		++ ans;
		T *a, *b;
		split(rt, 0, a, b);
		rt = merge0(a, b);
//		printf("%d\n", ans);
	}
	printf("%d\n", ans);
//	eprintf("time used: %.3f\n", clock() * 1.0 / CLOCKS_PER_SEC);
	return 0;
}