Ascending Photo

Time limit3sMemory limit512 MB

Summary

Given a sequence of n heights, find the minimum number of cuts so the pieces can be reordered into a nondecreasing sequence.

Level: Hard8 of 10
Topics: Greedy, Sorting, Dynamic programming, Array
Solved: No attempts yet

Problem

An amateur climbing club finished its 100th summit today. To mark the occasion, every member lined up in a single row for one photo.

The row is a mess, because the members stood wherever they felt like standing. We want to rearrange the photo so that the heights never decrease from left to right.

Figure: the photo after it was cut up and pasted back together to produce the answer to the first example.

The only thing we can do is cut the printed photo vertically between two neighbouring people and paste the resulting strips back together in any order. The people inside one strip keep their order.

Find the minimum number of cuts needed to paste the strips into one row whose heights never decrease from left to right.

Input

One line with the number of people in the photo, $n$ ( $1 \le n \le 10^6$ ).
One line with $n$ integers $h_1, \dots, h_n$ , the heights of the people from left to right ( $1 \le h_i \le 2 \times 10^9$ ).

Output

Output the minimum number of cuts needed to paste the strips into one row whose heights never decrease from left to right.

Examples3

Example 1
Input
```
11
3 6 12 7 7 7 7 8 10 5 5
```
Expected output
```
4
```
Example 2
Input
```
3
5000000 5500000 7000000
```
Expected output
```
0
```
Example 3
Input
```
12
1 2 2 3 3 1 2 3 4 1 2 3
```
Expected output
```
6
```