Cerința

Aflat pe plaja urbană din cartierul Cricozescu al orașului Jluc, Andrei participă la un concurs de construcții de castele de nisip. Fiecare concurent a construit deja un anumit număr de castele n, însă organizatorii concursului au schimbat regulile în ultimul moment, astfel că, pentru a fi eligibili în etapa de jurizare, toate castelele concurenților trebuie să aibă exact aceeași înălțime h, unde h este înălțimea unui castel deja construit de Andrei. Pentru a uniformiza înălțimile, concurenții trebuie să efectueze un număr de operații asupra unui castel, iar în cadrul unei operații există două posibilități:

• Fie se adaugă o lopată de nisip castelului curent – în acest caz, înâlțimea castelului crește cu 1cm;
• Fie se înlătură o lopată de nisip din vârful castelului – în acest caz, înălțimea castelului scade cu 1cm.

Având în vedere precizările făcute de organizatori la finalul concursului, Andrei ne cere să îl ajutăm să determine numărul minim de operații pe care el trebuie să le facă asupra castelelor sale astfel încât toate să aibă, în final, aceeași înălțime h, h fiind înălțimea inițială a unuia dintre castelele construite.

Date de intrare

Fișierul de intrare castele.in conține pe prima linie un număr natural n, reprezentând numărul de castele pe care Andrei le are, iar pe a doua linie se află n numere naturale, reprezentând înălțimile inițiale ale castelelor lui Andrei.

Date de ieșire

Fișierul de ieșire castele.out va conține pe singura linie numărul k, reprezentând numărul minin de operații pe care Andrei trebuie să le efectueze astfel încât castelele sale să aibă aceeași înălțime.

Restricții și precizări

• 1 ≤ n ≤ 100000;
• 1 ≤ h ≤ 1000, unde h reprezintă înălțimea unui castel;
• Pentru teste în valoare de 10 puncte, toate castelele au înălțimile egale.
• Pentru teste în valoare de 45 de puncte, n ≤ 1000.
• Pentru alte teste în valoare de 15 puncte, înălțimile castelelor sunt sortate crescător.
• Pentru alte teste în valoare de 30 de puncte, nu există restricții suplimentare.

Exemplu 1

castele.in

7
3 1 2 1 2 3 3

castele.out

5

Explicație

Avem 7 castele cu înălțimile: 3, 1, 2, 1, 2, 3, 3. Pentru a le aduce pe toate la aceeași înălțime, una dintre strategii posibile este să alegem înălțimea finală a castelelor ca fiind 2 (deși pot exista și alte înălțimi care duc la același număr minim de operații).

• Primul castel (3) necesită 1 operație pentru a ajunge la 2 (înlăturăm o lopată de nisip).
• Al doilea castel (1) necesită 1 operație pentru a ajunge la 2 (adăugăm o lopată de nisip).
• Al treilea (2) nu necesită nicio operație, este deja la înălțimea 2.
• Al patrulea (1) necesită 1 operație pentru a ajunge la 2.
• Al cincilea (2) este deja la 2.
• Al șaselea (3) necesită 1 operație pentru a ajunge la 2.
• Al șaptelea (3) necesită 1 operație pentru a ajunge la 2.

Numărul total de operații este 1 + 1 + 0 + 1 + 0 + 1 + 1 = 5.

Exemplu 2

castele.in

4
1 1 10 10

castele.out

18

Explicație

• Primele două castele (1 și 1) sunt deja la 1, deci 0 operații.
• Următoarele două (10 și 10) necesită câte 9 operații fiecare pentru a ajunge la 1 (înlăturăm câte o lopată de nisip de 9 ori pentru fiecare).

Totalul este 0 + 0 + 9 + 9 = 18 operații, iar acesta este numărul minim.