408606: GYM103202 F Kobolds and Catacombs

Kobolds are rat-like, candle-loving cave folk, digging deep beneath the surface for millennia. Today, they gather together in a queue to explore yet another tunnel in their catacombs!

But just before the glorious movement initiates, they have to arrange themselves in non-descending heights. The shortest is always the leader digging small holes, and the followers swelling it.

The kobolds are hyperactive; they like to move here and there. To make the arrangement easier, they decide to group themselves into consecutive groups first, then reorder in each group.

What's the maximum number of consecutive groups they can be partitioned into, such that after reordering the kobolds in each group in non-descending order, the entire queue is non-descending?

For example, given a queue of kobolds of heights [1, 3, 2, 7, 4], we can group them into three consecutive groups ([1] [3, 2] [7, 4]), such that after reordering each group, the entire queue can be non-descending.

The first line of the input contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$, denoting the number of kobolds.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots , a_n$$$ $$$(1 \le a_i \le 10^9)$$$, representing the heights of the kobolds in the queue.

Print a single integer, denoting the maximum number of groups.

5
1 3 2 7 4

3