Rendere uniformi le altezze
Per ottimizzare i costi, il dipartimento di progettazione urbana ti ha chiesto di aiutare a rendere tutti gli edifici della stessa altezza. Se tutti gli edifici hanno un’altezza uniforme, i costi di costruzione si riducono notevolmente.
In città sono presenti
n edifici, ciascuno con un’altezza diversa . Modificare l’altezza di un edificio di x comporta una riunione che durerà x minuti. Dato che hai poco tempo a disposizione, desideri minimizzare i minuti trascorsi in riunione. Qual è il minor tempo possibile da spendere in totale?Input
La prima riga dell’input contiene un unico intero
n (1 ≤ n ≤ ).La riga successiva contiene
n numeri interi separati da spazio (1 ≤ ≤ ), che rappresentano le altezze iniziali degli edifici.Output
Il programma deve stampare un singolo intero: il tempo minimo totale da trascorrere in riunione.
Examples
Input | Output |
5
1 4 8 2 9 | 14 |
Explanation
L’altezza ottimale in questo caso è 4 ⇒ occorre modificare 1 → 4 (riunione di 3 minuti), 2 → 4 (riunione di 2 minuti), 8 → 4 (riunione di 4 minuti), 9 → 4 (riunione di 5 minuti), per un totale di 14 minuti.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB