Problem Description

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.

Input Format

The first line contains an integer $N$.

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

Output Format

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

6
3 4 5 1 2 6

1

9
1 5 9 9 5 1 1 5 9

2

Hint

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<j \le N$), $A_i \ne A_j$.
6. ($46$ points) No additional constraints.

Translation completed by ChatGPT-5.6.

Translated by ChatGPT 5