Necessità di Ordine Non Decrescente
Data un array di
n interi, l’obiettivo è di renderlo non decrescente eseguendo la seguente operazione zero o più volte:Scegli un indice
i (1 ≤ i ≤ n) e sostituisci a_i con un qualunque intero.Lo scopo è minimizzare il numero di operazioni necessarie affinché l’array diventi non decrescente.
💡
Formalmente, un array è non decrescente se per tutti gli indici e tali che , vale .
Dati in Ingresso
La prima riga dei dati in ingresso contiene un singolo intero
n (1 ≤ n ≤ 100 000), che rappresenta la lunghezza dell’array.La seconda riga contiene
n interi separati da uno spazio (1 ≤ ≤ ).Dati in Uscita
Il programma deve stampare un unico intero: il numero minimo di operazioni necessarie per rendere l’array non decrescente.
Esempi
Ingresso | Uscita |
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