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>
using namespace std;

#define ls tree[node].l
#define rs tree[node].r

mt19937 rnd( time(NULL) );

const int maxN = 4e5 + 10;

struct Treap
{
	int l, r;
	int key, val, size;
}tree[maxN + 1];

int n, cnt, m, lim;
int a[maxN + 1], mx[maxN * 4 + 1];
int root[maxN + 1];

vector<int> t;

inline int read()
{
	int num = 0, f = 1;
	char ch = getchar();
	while( !isdigit( ch ) ) { if(ch == '-') f = -1; ch = getchar(); }
	while( isdigit( ch ) ) num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
	return num * f;
}

inline int new_Node(int v)
{
	tree[++ cnt] = (Treap){0, 0, (int)rnd(), v, 1};
	return cnt;
}

inline void pushup(int node)
{
	tree[node].size = tree[ls].size + tree[rs].size + 1;
}

inline void split(int node, int k, int &u, int &v)
{
	if(!node) { u = v = 0; return; }
	if(tree[node].val <= k) u = node, split(rs, k, tree[u].r, v);
	else v = node, split(ls, k, u, tree[v].l);
	pushup(node);
}

inline int merge(int u, int v)
{
	if(!u || !v) return u | v;
	if(tree[u].key < tree[v].key)
	{
		tree[u].r = merge(tree[u].r, v);
		pushup(u);
		return u;
	}
	else
	{
		tree[v].l = merge(u, tree[v].l);
		pushup(v);
		return v;
	}
}

inline int find(int node)
{
	while(rs) node = rs;
	return node ? tree[node].val : 0;
}

inline void change(int node, int l, int r, int x, int num)
{
	if(l == r) { mx[node] = num; return; }
	int mid = (l + r) >> 1;
	if(x <= mid) change(node << 1, l, mid, x, num);
	else change(node << 1 | 1, mid + 1, r, x, num);
	mx[node] = max(mx[node << 1], mx[node << 1 | 1]);
}

inline int query(int node, int l, int r, int v)
{
	if(mx[node] < v) return v;
	if(l == r) { t.push_back(l); return mx[node]; }
	int mid = (l + r) >> 1, res = v;
	if(res < mx[node << 1]) res = query(node << 1, l, mid, res);
	if(res < mx[node << 1 | 1]) res = query(node << 1 | 1, mid + 1, r, res);
	return res;
}

int main()
{
	n = read(); lim = 2 * n;
	for(int i = 1; i <= n; i++) a[i] = read();

	m = 1;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] < a[i - 1]) m ++;
		root[m] = merge(root[m], new_Node(a[i]));
	}

	for(int i = 1; i <= m; i++) change(1, 1, lim, i, find(root[i]));

	for(int i = 0; i < n; i++)
	{
		t.clear();
		query(1, 1, lim, 0);
		m ++;
		int val = 0;
		for(int j = 0; j < t.size(); j++)
		{
			int x = t[j], u = 0, v = 0;
			split(root[x], val, u, v);
			root[m] = merge(root[m], v);
			root[x] = u;
			change(1, 1, lim, x, find(u));
			if(v) val = find(v);
		}
		change(1, 1, lim, m, find(root[m]));
		if(tree[ root[m] ].size == n)
		{
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}