{"problem":{"name":"Strange Sorting","description":{"content":"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)$: *   Fi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc014_f"},"statements":[{"statement_type":"Markdown","content":"Takahashi loves sorting.\nHe 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)$:\n\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.\n*   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**.\n*   Lastly, rearrange the permutation into $(b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k)$.\n\nHow many operations are necessary until the permutation is sorted?\n\n## Constraints\n\n*   $1 ≤ N ≤ 2×10^5$\n*   $(p_1,p_2,...,p_N)$ is a permutation of the integers from $1$ through $N$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$p_1$ $p_2$ ... $p_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc014_f","tags":[],"sample_group":[["5\n3 5 1 2 4","3\n\nThe initial permutation is $(3,5,1,2,4)$, and each operation changes it as follows:\n\n*   In the first operation, the $1$\\-st and $2$\\-nd elements are high, and the $3$\\-rd, $4$\\-th and $5$\\-th are low. The permutation becomes: $(1,2,4,3,5)$.\n*   In the second operation, the $1$\\-st, $2$\\-nd, $3$\\-rd and $5$\\-th elements are high, and the $4$\\-th is low. The permutation becomes: $(3,1,2,4,5)$.\n*   In the third operation, the $1$\\-st, $4$\\-th and $5$\\-th elements are high, and the $2$\\-nd and $3$\\-rd and $5$\\-th are low. The permutation becomes: $(1,2,3,4,5)$."],["5\n5 4 3 2 1","4"],["10\n2 10 5 7 3 6 4 9 8 1","6"]],"created_at":"2026-03-03 11:01:14"}}