Requisito de no decrecencia
Dado un arreglo de
n números enteros, se te solicita convertir el arreglo en uno que no sea decreciente, realizando la siguiente operación cero o más veces:Elige cualquier índice
i (1 ≤ ≤ n) y reemplaza con cualquier número entero.El objetivo es minimizar la cantidad de operaciones necesarias para que el arreglo no sea decreciente.
💡
Formalmente, un arreglo es no decreciente si para todo y tales que , se cumple .
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ 100 000), que es la longitud del arreglo.La segunda línea contiene
n números enteros separados por espacios (1 ≤ ≤ ).Salida
El programa debe imprimir un único entero: el número mínimo de operaciones necesarias para que el arreglo no sea decreciente.
Examples
Entrada | Salida |
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