Rearrange Segments for Sorted Memory Blocks

Felix is working on his startup project, SuperFastZilla, where storage fragmentation might be slowing things down. The storage consists of n memory blocks, where the i-th block is used in the a_i-th operation. Felix would like to sort the blocks by their operation indices. However, due to how the storage is arranged, he is allowed only to split the storage into contiguous segments and then rearrange these segments arbitrarily (without changing the order of blocks inside a segment) to obtain a non‐decreasing sequence of operation indices.

More formally, given an array a of length n, Felix can split it into several contiguous segments. By permuting these segments (keeping each segment intact), he wants to achieve an array that is sorted in non–decreasing order. Your task is to help Felix by finding the minimum number of segments into which the array may be split so that after some rearrangement, the whole array is sorted.

It can be shown that the answer is equal to the number of parts when the sorted order is compared with the original order as follows. Let b be the sorted version of a (using a stable sort so that equal elements appear in the same order as in a). Denote by idx the array of original indices of the elements in a ordered as in b. Then, the answer is 1 plus the number of positions i (1 ≤ i < n) for which idx[i+1] < idx[i].

For example, if a = [2, 3, 1, 1, 2, 2, 1], then b = [1, 1, 1, 2, 2, 2, 3]. A possible assignment of positions (using 1–based indexing) is idx = [3, 4, 7, 1, 5, 6, 2]. We see that there are 2 positions where the order decreases, so the minimal number of segments is 3. These segments can be rearranged to form the sorted sequence.

inputFormat

The first line contains an integer n (the number of memory blocks).
The second line contains n integers a₁, a₂, ..., a_n (the operation indices for each block), separated by spaces.

outputFormat

Output a single integer, the minimum number of segments into which the array can be split so that by permuting these segments one can obtain a non–decreasing sequence.

sample

7
2 3 1 1 2 2 1

3