Sorting

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence of N integers, find the minimum number of contiguous blocks that can be reordered as whole blocks to produce a sorted sequence.

Level: Medium6 of 10
Topics: Array, Greedy, Sorting
Solved: No attempts yet

Problem

A sequence $A_1, A_2, \dots, A_N$ is called sorted if $A_i \le A_{i+1}$ holds for every $1 \le i < N$ .

Consider the following way to sort a sequence. First, split the sequence into $M$ blocks: the first $k_1$ elements form the first block, the next $k_2$ elements form the second block, and so on, until the last $k_M$ elements form the last block. Then you may swap whole blocks with each other, but you may not change the order of elements inside any block.

Depending on how the blocks are chosen, swapping blocks may or may not be enough to sort the sequence. For example, if the whole sequence is one block, only a sequence that is already sorted can be sorted. Splitting an $N$ -element sequence into $N$ blocks always works.

Find the minimum $M$ such that some split into $M$ blocks lets the whole sequence be sorted by swapping blocks.

Input

The first line contains the number of elements $N$ ( $1 \le N \le 500\,000$ ). The second line contains the elements $A_1, A_2, \dots, A_N$ ( $1 \le A_i \le N$ ), separated by spaces.

Output

Print one integer on a single line: the minimum number of blocks $M$ that lets the sequence be sorted by swapping blocks.

Examples2

Example 1
Input
```
6
5 6 4 3 1 2
```
Expected output
```
4
```
Example 2
Input
```
3
1 2 1
```
Expected output
```
2
```