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 <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct Node {
	Node *l = 0, *r = 0;
	int val, y;
	int first, max;
	bool monotone;
	Node(int val) : val(val), y(rand()) {
		first = max = val;
		monotone = 1;
	}
	void reset() {
		first = max = val;
		monotone = 1;
	}
	void recalc();
	void recalc3();
};

inline void Node::recalc() {
	first = l ? l->first : val;
	int max = val;
	bool mon = 1;
	if (l) {
		max = std::max(max, l->max);
		if (!l->monotone || l->max > val) mon = 0;
	}
	if (r) {
		max = std::max(max, r->max);
		if (mon && (!r->monotone || r->first < val)) mon = 0;
	}
	this->max = max;
	monotone = mon;
}

inline void Node::recalc3() {
	first = l ? l->first : val;
	int max = val;
	if (l) {
		max = std::max(max, l->max);
	}
	if (r) {
		max = std::max(max, r->max);
	}
	this->max = max;
	monotone = 1;
}

Node* merge2(Node* l, Node* r) {
	if (l->y > r->y) {
		l->r = l->r ? merge2(l->r, r) : r;
		l->recalc();
		return l;
	} else {
		r->l = r->l ? merge2(l, r->l) : l;
		r->recalc();
		return r;
	}
}

inline Node* merge(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	return merge2(l, r);
}

Node* merge32(Node* l, Node* r) {
	if (l->y > r->y) {
		l->r = l->r ? merge32(l->r, r) : r;
		l->recalc3();
		return l;
	} else {
		r->l = r->l ? merge32(l, r->l) : l;
		r->recalc3();
		return r;
	}
}

inline Node* merge3(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	return merge32(l, r);
}

pair<Node*, Node*> split2(Node* n, int lo) {
	if (!n) return {0, 0};
	if (n->max < lo) return {0, n};
	if (n->monotone) {
		if (lo < n->first) return {n, 0};
		if (!n->l) {
			if (!n->r) return {0, n};
			assert(lo >= n->val);
			auto pa = split2(n->r, lo);
			n->r = 0;
			n->reset();
			pa.second = merge(n, pa.second);
			return pa;
		}

		if (lo < n->val) {
			auto pa = split2(n->l, lo);
			n->l = 0;
			n->recalc();
			pa.first = merge3(pa.first, n);
			return pa;
		}
		else {
			// if (!n->r) return {0, n};
			auto pa = split2(n->r, lo);
			n->r = 0;
			n->recalc();
			pa.second = merge(n, pa.second);
			return pa;
		}
	}

	Node *left = n->l, *right = n->r;
	n->l = n->r = 0;
	n->recalc();
	auto pa = split2(left, lo);
	if (pa.first) lo = pa.first->max;
	if (n->val > lo) {
		pa.first = merge3(pa.first, n);
		lo = n->val;
	}
	else {
		pa.second = merge(pa.second, n);
	}
	auto pa2 = split2(right, lo);
	return {merge3(pa.first, pa2.first), merge(pa.second, pa2.second)};
}

int main() {
	srand(2);
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N;
	cin >> N;
	vector<Node> nodes;
	rep(i,0,N) {
		int p;
		cin >> p;
		nodes.emplace_back(p);
	}

	Node* t = 0;
	rep(i,0,N)
		t = merge(t, &nodes[i]);

	int res = 0;
	while (!t->monotone) {
		++res;
		auto pa = split2(t, 0);
		t = merge(pa.second, pa.first);
	}

	cout << res << endl;
	exit(0);
}