Heavy Blocks

Time limit1sMemory limit128 MB

Summary

Topple n distinct-weight blocks with the fewest pushes when each push fells lighter neighbors in one direction until a heavier block or gap.

Level: Hard8 of 10
Topics: Dynamic programming, Stack, Tree, Divide and conquer
Solved: No attempts yet

Problem

There are $n$ blocks standing in a row, numbered from left to right. Each block has a distinct positive-integer weight.

When you push a standing block to the left or to the right, it topples. Toppling spreads like dominoes in the chosen direction, knocking over each consecutive block on that side that is lighter than the pushed block. The chain stops as soon as it reaches a block heavier than the pushed block (that heavier block stays standing) or a position where a block has already fallen. The pushed block itself always topples.

Each move pushes one standing block in one direction. Find the minimum number of pushes needed to topple every block.

Input

The first line contains an integer $n$ , the number of blocks ( $1 \le n \le 10^6$ ).

The second line contains $n$ distinct integers, the weights of the blocks from left to right, each between $1$ and $10^9$ .

Output

Print a single integer: the minimum number of pushes needed to topple all the blocks.

Examples3

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