Algorithms and Data Structures

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

To check your solution you need to sign in
Sign in to continue