Rendi la sequenza non decrescente
Supponiamo di avere un array di
n interi che devi trasformare in una sequenza non decrescente. Hai la possibilità di aggiungere 1 a qualsiasi elemento dell’array tutte le volte che vuoi. Ogni volta che aggiungi 1 a un elemento, paghi $1. L’obiettivo è rendere l’array non decrescente con il costo più basso possibile. Riesci a calcolare qual è il costo minimo necessario per effettuare questa trasformazione?Input
La prima riga dell’input contiene un singolo intero
n (2 ≤ n ≤ ), che rappresenta il numero di elementi nell’array.La seconda riga dell’input contiene
n interi separati da spazi, ( ≤ ≤ ), i quali costituiscono gli elementi dell’array.Output
Il programma deve stampare il costo minimo per trasformare l’array in una sequenza non decrescente.
Esempi
Input | Output |
4
-2 3 1 0 | 5 |
5
1 2 3 4 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB