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 <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

unsigned long xor128() {
        static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
        unsigned long t = (x ^ (x << 11));
        x = y; y = z; z = w;
        return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

static const int INF = 0x3f3f3f3f;

struct node_t {
        node_t *l = NULL, *r = NULL;
        int val, first, ma;
        int pri;
        bool monotone;
        node_t(int val) : val(val), pri(xor128() % INF) {
                first = ma = val;
                monotone = true;
        }
        void reset() {
                first = ma = val;
                monotone = true;
        }
        void update() {
                first = (l ? l->first : val);
                int tmpma = val;
                bool tmpmonotone = true;
                if (l) {
                        tmpma = max(tmpma, l->ma);
                        if (!l->monotone || l->ma > val) tmpmonotone = false;
                }
                if (r) {
                        tmpma = max(tmpma, r->ma);
                        if (tmpmonotone && (!r->monotone || val > r->first)) tmpmonotone = false;
                }
                ma = tmpma;
                monotone = tmpmonotone;
        }
        void update2() {
                first = (l ? l->first : val);
                ma = (r ? r->ma : val);
                monotone = true; 
        }
};

inline node_t* merge(node_t *l, node_t *r) {
        if (!l) return r;
        if (!r) return l;
        if (l->pri > r->pri) {
                l->r = l->r ? merge(l->r, r) : r;
                l->update();
                return l;
        } else {
                r->l = r->l ? merge(l, r->l) : l;
                r->update();
                return r;
        }
}

inline node_t* merge2(node_t *l, node_t *r) {
        if (!l) return r;
        if (!r) return l;
        if (l->pri > r->pri) {
                l->r = l->r ? merge2(l->r, r) : r;
                l->update2();
                return l; 
        } else {
                r->l = r->l ? merge2(l, r->l) : l;
                r->update2();
                return r;
        }
}

pair<node_t*, node_t*> split(node_t *tree, int lb) {
        if (!tree) return { NULL, NULL };
        if (tree->ma < lb) return { NULL, tree };
        if (tree->monotone) {
                if (lb < tree->first) return { tree, NULL };
                else if (!tree->l) {
                        if (!tree->r) return { NULL, tree };
                        auto sub = split(tree->r, lb);
                        tree->r = NULL;
                        tree->reset();
                        sub.second = merge(tree, sub.second);
                        return sub;
                } else if (lb < tree->val) {
                        auto sub = split(tree->l, lb);
                        tree->l = NULL;
                        tree->update();
                        sub.first = merge2(sub.first, tree);
                        return sub;
                } else {
                        auto sub = split(tree->r, lb);
                        tree->r = NULL;
                        tree->update();
                        sub.second = merge(tree, sub.second);
                        return sub;
                }
        } else {
                node_t *left = tree->l, *right = tree->r;
                tree->l = tree->r = NULL;
                tree->update();
                auto sub = split(left, lb);
                if (sub.first) {
                        lb = sub.first->ma;
                }
                if (tree->val > lb) {
                        sub.first = merge2(sub.first, tree);
                        lb = tree->val;
                } else {
                        sub.second = merge(sub.second, tree);
                }
                auto sub2 = split(right, lb);
                return { merge2(sub.first, sub2.first), merge(sub.second, sub2.second) };
        }
}

/*
void dfs(node_t* u) {
        if (u->l) dfs(u->l);
        cerr << u->val << ' ';
        if (u->r) dfs(u->r);
}
*/

int main() {
        int n;
        scanf("%d", &n);
        vector<node_t> nodes;
        for (int i = 0; i < n; i ++) {
                int p;
                scanf("%d", &p);
                nodes.emplace_back(p);
        }
        node_t* tree = NULL;
        for (int i = 0; i < n; i ++) {
                tree = merge(tree, &nodes[i]);
        }
        int ans = 0;
        /*
        dfs(tree);
        cerr << endl;
        */
        while (!tree->monotone) {
                ans ++;
                auto sub = split(tree, 0);
                tree = merge(sub.second, sub.first);
                /*
                dfs(tree);
                cerr << endl;
                */
        }
        printf("%d\n", ans);
        return 0;
}