Laser

Cerință

În cadrul Centrului de Cercetare „NovaTech”, o echipă tehnică trebuie să transporte către centrul de reciclare un set de $n$ nuclee energetice, numerotate $1,2,3, ...,n$, aliniate într-un coridor magnetic, fiecare nucleu având un anumit nivel natural de energie (număr natural nenul). Pentru siguranța transportului, toate nucleele trebuie neutralizate, adică aduse la nivelul 0 de energie. Singura unealtă disponibilă este $Laserul$ $Nivelelor$, un dispozitiv de precizie, care poate reduce nivelele de energie ale nucleelor. Laserul se activează când întâlnește un nucleu cu valoarea maximă, căruia îi reduce nivelul de energie exact cât să ajungă la următorul nivel maxim existent, mai mic strict decât el (sau la 0, dacă nu mai există un nivel inferior). Dacă mai multe nuclee au aceeași valoare maximă, laserul le tratează individual, reducându-le nivelele de energie, pe rând, în același mod. După ce toate nucleele cu nivel de energie maxim sunt reduse, conform descrierii de mai sus, valoarea maximă de energie se modifică, aceasta fiind cea la care a fost redus maximul anterior. Operațiile de activare a laserului pentru reducerea nivelelor maxime curente se repetă până când toate nucleele ajung la nivelul 0. Să se determine numărul total de activări ale Laserului Nivelelor, necesare pentru a reduce toate nucleele la nivelul 0.

Date de intrare

Pe prima linie a fișierului de intrare laser.in se află un număr natural $n$, reprezentând numărul de nuclee, iar pe a doua linie, separate prin câte un spațiu, n numere naturale nenule, $e$1, $e$2, ..., $e$$n$, reprezentând nivelurile de energie ale nucleelor, în ordinea în care sunt aliniate.

Date de ieșire

Pe prima linie a fișierului de ieșire laser.out se va găsi un singur număr întreg, numărul total de activări ale laserului.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$;
• $1 \leq e1, e2, ..., en \leq 1 \ 000 \ 000 \ 000$;
• pentru teste în valoare de $56$ de puncte avem $n \leq 1 \ 000$;
• pentru teste în valoare de $39$ de puncte nivelurile de energie sunt valori cel mult egale cu $1 \ 000 \ 000$;
• pentru teste în valoare de $16$ puncte nivelurile de energie sunt valori distincte;

Exemplul 1

laser.in

6
7 3 3 5 7 3

laser.out

11

Explicație

Primul nucleu cu 7, scade la 5 → 1 activare
Al doilea nucleu cu 7, scade la 5 → 1 activare
Toate nucleele cu 5 (trei la număr acum), scad la 3 → 3 activări
Toate nucleele cu 3 (șase la număr acum), scad la 0 → 6 activări
Total activări: 1 + 1 + 3 + 6 = 11

Exemplul 2

laser.in

4
9 9 9 9 

laser.out

4

Explicație

Toate nucleele cu 9 (patru la număr), scad la 0 → 4 activări