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 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 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: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB