405896: GYM102154 B Decryption

If you keep the first and the last letter of a word unchanged and rearrange other letters arbitrarily, the resulting word should still be readable. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

We will explore a similar phenomenon with sequences of sorted numbers after scrambling elements in the middle.

Let's call a sequence of integers correct if the first number is the smallest in the sequence and the last number — largest. For example, sequences $$$[1, 3, 2, 4]$$$ and $$$[1, 2, 1, 2]$$$ are correct, while $$$[1, 3, 2]$$$ and $$$[2, 1, 2]$$$ are not.

There is a sequence of $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$. We want to split it into the minimum number of correct segments. For example, the sequence $$$[2, 3, 1, 1, 5, 1]$$$ can be splitted into three correct segments: $$$[2, 3]$$$, $$$[1, 1, 5]$$$ and $$$[1]$$$.

Determine the minimum possible number of correct segments that the sequence can be split into.

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the size of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the elements of the sequence ($$$1 \le a_i \le 10^9$$$).

Print one integer — the minimum possible number of correct segments that the sequence can be split into.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 30 & n \le 500 & 0 \\ \hline 2 & 30 & n \le 5\,000 & 0, 1 \\ \hline 3 & 40 & n \le 300\,000 & 0, 1, 2 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

5
5 4 3 2 1

5

4
1 3 2 4

1

6
2 3 1 1 5 1

3