# Non-Decreasing Necessity

Given an array of

`n`

integers, you are asked to make the array non-decreasing by performing the following operation zero or more times:Choose any index

`i`

(1 β€ i β€ n) and replace

with any integer.Your goal is to minimize the number of operations required to make the array non-decreasing.

π‘

Formally, an array is non-decreasing if for all and such that , we have .

Input

The first line of the input contains a single integer

`n`

(1 β€ n β€ 100 000), the length of the array.The second line contains

`n`

space-separated integers

(1 β€ β€ ). Output

The program should print a single integer β the minimum number of operations required to make the array non-decreasing.

Examples

Input | Output |

7
1 3 2 2 7 4 3 | 3 |

4
1 2 1 4 | 1 |

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB