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;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

const int maxN = 524288 + 233;
int n, val[maxN];

vector<int> idx;
struct Seg {
	int mx[maxN * 2], n;
	void init(int len) {
		memset(mx, 0, sizeof(mx));
		n = len;
		while(__builtin_popcount(n) > 1)
			n += n & -n;
	}
	void reset(int i, int val) {
		i = i + n - 1;
		mx[i] = val;
		while((i /= 2) >= 1) mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
	}
	void get(int o, int L, int R, int ql, int qr, int &t) {
//		eprintf("[%d, %d]: t = %d, val = %d\n", L, R, t, mx[o]);
		if(t >= mx[o]) return;
		
		if(ql <= L && R <= qr) {
			if(L == R) idx.push_back(L), t = mx[o], assert(o == L - 1 + n);
			else {
				int M = (L + R) >> 1;
				get(o * 2, L, M, ql, qr, t);
				get(o * 2 + 1, M + 1, R, ql, qr, t);
			}
		} else {
			int M = (L + R) >> 1;
			if(ql <= M) get(o * 2, L, M, ql, qr, t);
			if(qr > M) get(o * 2 + 1, M + 1, R, ql, qr, t);
		}
	}
	void get(int l, int r) {
		int t = 0;
		get(1, 1, n, l, r, t);
	}
} seg;

struct Node {
	Node *ch[2];
	int v, s;
	Node(int val = 0) { ch[0] = ch[1] = nullptr; v = val; s = 1; }
	void maintain() {
		s = 1;
		if(ch[0]) s += ch[0]->s;
		if(ch[1]) s += ch[1]->s;
	}
	int max() {
		if(ch[1]) return ch[1]->max();
		else return v;
	}
};

void split(Node *o, Node* &L, Node* &R, int t) { // val(L) <= t
	if(o == nullptr) L = R = nullptr;
	else if(o->v <= t) {
		L = o;
		split(o->ch[1], L->ch[1], R, t);
		L->maintain();
	} else {
		R = o;
		split(o->ch[0], L, R->ch[0], t);
		R->maintain();
	}
}
mt19937 e(2333);
Node* merge(Node *L, Node *R) {
	if(L == nullptr) return R;
	else if(R == nullptr) return L;
	else {
		int prob = e() % (L->s + R->s);
		if(prob < L->s) {
			Node *o = L;
			o->ch[1] = merge(L->ch[1], R);
			o->maintain();
			return o;
		} else {
			Node *o = R;
			o->ch[0] = merge(L, R->ch[0]);
			o->maintain();
			return o;
		}
	}
}
Node pool[maxN];
Node* nodes[maxN];

void dfs(Node *o) {
	if(!o) return;
	dfs(o->ch[0]);
	printf("%d ", o->v);
	dfs(o->ch[1]);
} 

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> val[i];
	seg.init(n * 2);
	
	for(int i = 1; i <= n; ++i)
		nodes[i] = pool + i,
		*nodes[i] = Node(val[i]),
		seg.reset(i, val[i]);
		
	for(int i = n + 1; i <= 2 * n; ++i) {
		idx.clear();
		seg.get(1, i);
//		displaya(val, 1, i);
//		displayv(idx);
		int last = 0;
		nodes[i] = nullptr;
		for(int j : idx) {
//			display(j); display(last);
			Node *L, *R;
			split(nodes[j], L, R, last);
			last = val[j];
			nodes[j] = L;
			if(L) val[j] = L->max();
			else val[j] = 0;
			seg.reset(j, val[j]);
			nodes[i] = merge(nodes[i], R);
		}
		val[i] = nodes[i]->max();
		seg.reset(i, val[i]);
		if(nodes[i]->s == n) {
			cout << (i - n - 1) << endl;
			return 0;
		}
//		for(int t = 1; t <= i; ++t) {
//			eprintf("tree[%d]: ", t);
//			dfs(nodes[t]);
//			eprintf("\n");
//		}
	}
	assert(false);
	return 0;
}