P17136 [KOI 2026 #1] Sequence Sorting

You are given a sequence $A = [A_1, A_2, \ldots, A_N]$ of length $N$. You may perform the following operation any number of times, possibly $0$ times: 1. Choose a positive integer $x$. 2. From sequence $A$, take all elements with values not greater than $x$, keeping their relative order from the original sequence, forming a subsequence $B$. 3. From sequence $A$, take all elements with values greater than $x$, keeping their relative order from the original sequence, forming a subsequence $C$. 4. Replace the original sequence $A$ with the sequence obtained by concatenating $B$ and $C$ in order, i.e., $B+C$. Write a program to compute the minimum number of operations needed to sort sequence $A$ in non-decreasing order, i.e., to satisfy $A_1 \le A_2 \le \cdots \le A_N$. It can be proven that for all inputs satisfying the constraints, the given sequence can always be sorted into non-decreasing order using the operations above.

The first line contains an integer $N$. The second line contains $N$ integers $A_1,A_2,\ldots,A_N$, separated by spaces.

Output a single integer on the first line, indicating the minimum number of operations required to sort sequence $A$ in non-decreasing order.

### Sample Explanation 1 You can sort sequence $A$ into non-decreasing order using $1$ operation as follows. 1. Let $x=2$. Keeping the original relative order, extract all elements with values not greater than $x=2$, obtaining $B:=[1,2]$. Keeping the original relative order, extract all elements with values greater than $x=2$, obtaining $C:=[3,4,5,6]$. Therefore, sequence $A$ is replaced by $B+C=[1,2,3,4,5,6]$. ### Sample Explanation 2 You can sort sequence $A$ into non-decreasing order using $2$ operations as follows. 1. Let $x=3$. Keeping the original relative order, extract all elements with values not greater than $x=3$, obtaining $B:=[1,1,1]$. Keeping the original relative order, extract all elements with values greater than $x=3$, obtaining $C:=[5,9,9,5,5,9]$. Therefore, sequence $A$ is replaced by $B+C=[1,1,1,5,9,9,5,5,9]$. 2. Let $x=7$. Keeping the original relative order, extract all elements with values not greater than $x=7$, obtaining $B:=[1,1,1,5,5,5]$. Keeping the original relative order, extract all elements with values greater than $x=7$, obtaining $C:=[9,9,9]$. Therefore, sequence $A$ is replaced by $B+C=[1,1,1,5,5,5,9,9,9]$. It can be proven that it is impossible to sort sequence $A$ into non-decreasing order using fewer than $2$ operations. ### Constraints - All numbers given in the input are integers. - $1 \le N \le 300\,000$. - For each integer $i$ ($1 \le i \le N$), $1 \le A_i \le N$. ### Subtasks 1. ($6$ points) For each integer $i$ ($1 \le i \le N$), $A_i \le 2$. 2. ($15$ points) $N \le 15$. 3. ($23$ points) $N \le 100$. 4. ($27$ points) $N \le 750$. 5. ($33$ points) For any integers $i,j$ ($1 \le i