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.

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