Fragmentation

Felix is building a startup project in his garage. He already has a name for it: SuperFastZilla. He has not decided what SuperFastZilla should do, but he is sure that it has to run fast.

One day Felix noticed that SuperFastZilla runs too slowly even though it uses fast algorithms. He thinks fragmented storage is the cause.

The storage that SuperFastZilla uses consists of $n$ memory blocks. Each block is used by exactly one operation, and the $i$-th block is used by operation $a_i$.

Felix wants to sort the blocks by the number of the operation that uses them. To do it quickly, he cuts the storage into segments of consecutive blocks and then changes only the order of the segments to build the sorted array. He can cut wherever he likes and can concatenate the segments in any order, but he cannot change the order of the blocks inside a segment. After the segments are joined again, the operation numbers must be non-decreasing.

Find the smallest possible number of segments.

For example, with $a = [2, 3, 1, 1, 2, 2, 1]$ you can cut the storage into $[2, 3]$, $[1, 1, 2, 2]$ and $[1]$, then join them in the order $[1]$, $[1, 1, 2, 2]$, $[2, 3]$ to get the sorted array. Two segments are not enough, so the smallest number is 3.

The first line contains the number of blocks $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces ($1 \le a_i \le 10^5$).

Print the minimum number of segments on one line.