Code Lock

Interview

Time limit2sMemory limit1024 MB

Summary

Given n displays where pressing button i copies display i+1 into display i, find the fewest presses that make the sequence non-decreasing.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Statement

To get into the secret base where Dr. No is hiding, James Bond has to crack a combination lock. Cryptography and lock cracking are not part of his job, so he asked you for help.

The lock has $n$ displays, and each display shows a number $a_i$ . Under every display except the last one is a large red button. Pressing the button under display $i$ replaces the number on display $i$ with the number currently shown on display $i+1$ .

Bond can get into the base only when the numbers on the displays form a non-decreasing sequence. Find the minimum number of button presses needed to reach such a state.

Input

The first line contains one integer $n$ ( $1 \le n \le 100000$ ), the number of displays. The second line contains $n$ integers $a_i$ ( $1 \le a_i \le 100000$ ), the numbers shown on the displays before the lock is cracked.

Output

Print one integer, the answer to the problem.

Examples1

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