Pădure

Dacii Dezlănțuiți au descoperit faptul că Mihai Eminescu este în viață și este ținut în captivitate de către antidaci într-un buncăr din Pădurea Hoia. Liderul lor, Feliciu Graur, a hotărât să inițieze o luptă pentru eliberarea Poetului.
Dacii vor porni către câmpul de luptă unul câte unul. Un dac nu dezertează înainte de a ajunge pe câmpul de luptă dacă și numai dacă dacul care a pornit înaintea lui este mai puternic decât el.
Feliciu dorește să îi trimită într-o ordine din care rezultă o putere totală cât mai mare în timpul luptei. Aflați puterea totală maximă.

Date de intrare

Fișierul de intrare padure.in va conține pe prima linie numărul întreg $N$, reprezentând numărul dacilor, iar pe a doua linie numerele întregi $p_1, p_2, ..., p_N$ , separate prin câte un spațiu, reprezentând puterea fiecărui dac.

Date de ieșire

Fișierul de ieșire padure.out va conține un număr întreg, reprezentând puterea totală maximă care poate fi obținută în luptă.

Restricții și precizări

• $1 \leq N \leq 10^5$
• $1 \leq p_i \leq 10^9, \forall i \in [1, n]$
• Pentru teste în valoare de $20$ de puncte, $N \leq 10^3$ și $p_i \leq 10^4, \forall i \in [1, n]$.
• Pentru alte teste în valoare de $30$ de puncte, $p_i \leq 10^7, \forall i \in [1, n]$.
• Pentru alte teste în valoare de $10$ puncte, $p_1, p_2, ..., p_N$ sunt distincte.
• Pentru alte teste în valoare de $40$ de puncte, nu există restricții suplimentare.
• Puterea totală în luptă este egală cu suma puterilor dacilor prezenți pe câmpul de luptă.
• Primul dac care pleacă către câmpul de luptă va dezerta.
• Liderul nu participă la luptă și nu este inclus în cei $N$ daci din fișierul de intrare.

Exemplul 1

padure.in

2
4 4

padure.out

0

Exemplul 2

padure.in

3
5 3 5

padure.out

3

Exemplul 3

padure.in

4
2 2 2 1

padure.out

1

Exemplul 4

padure.in

4
1 15 15 1

padure.out

2

Explicații

În primul exemplu, ambii daci vor dezerta, în orice ordine ar fi trimiși. Primul dac care pleacă dezertează întotdeauna (vezi a doua observație). Al doilea dac care pleacă va dezerta deoarece puterea sa $(4)$ va fi egală cu puterea dacului care a plecat înaintea lui $(4)$, oricare ar fi ordinea în care sunt trimiși.
În al doilea exemplu, Feliciu poate maximiza puterea totală trimițând la luptă întâi primul dac din fișierul de intrare (putere $5$), apoi pe al treilea (putere $5$), apoi pe al doilea (putere $3$). Primul dac care pleacă dezertează întotdeauna (vezi a doua observație). Al doilea dac care pleacă va dezerta deoarece are puterea $5$, iar cel care a plecat înaintea lui are tot puterea $5$, iar $5$ nu este mai mare decât $5$. Ultimul dac care pleacă nu va dezerta, deoarece cel care a plecat înaintea lui are o putere $(5)$ mai mare decât a sa $(3)$.
Cum doar ultimul dac care pleacă ajunge la luptă, puterea totală este egală cu puterea lui, care este $3$.
Nicio ordine nu rezultă într-o putere totală mai mare decât $3$.
În al treilea exemplu, Feliciu poate maximiza puterea totală trimițând la luptă dacii în ordinea din fișierul de intrare. Primul dac care pleacă dezertează întotdeauna (vezi a doua observație). Al doilea care pleacă va dezerta deoarece are puterea $2$, iar cel care a plecat înaintea lui are tot puterea $2$, deci nu este mai puternic decât el. Al treilea va dezerta din acelaşi motiv. Ultimul dac care pleacă nu va dezerta, deoarece cel care a plecat înaintea lui are o putere $(2)$ mai mare decât a sa $(1)$. Cum doar ultimul dac trimis ajunge la luptă, puterea totală este egală cu puterea lui, care este $1$. Nicio ordine nu rezultă într-o putere totală mai mare decât $1$.
În al patrulea exemplu, Feliciu poate maximiza puterea totală trimițând la luptă întâi al doilea dac din fișierul de intrare (putere $15$), apoi pe ultimul (putere $1$), apoi pe al treilea (putere $15$), apoi pe primul (putere $1$). Primul dac care pleacă dezertează întotdeauna (vezi a doua observație). Al doilea dac care pleacă nu va dezerta deoarece are puterea $1$, iar cel care a plecat înaintea lui are puterea $15$, deci este mai puternic $(15 > 1)$. Al treilea dac care pleacă va dezerta deoarece are puterea $15$, iar cel care a plecat înaintea lui are puterea $1$, deci nu este mai puternic ($1$ nu este mai mare decât $15$). Ultimul dac care pleacă nu va dezerta, deoarece cel care a plecat înaintea lui are o putere $(15)$ mai mare decât a sa $(1)$. Cum al doilea și al patrulea dac (în ordinea în care pleacă) sunt cei care ajung la luptă, ceilalți doi dezertând, puterea totală este egală cu suma puterilor lor: $1+1=2$. Nicio ordine nu rezultă într-o putere totală mai mare decât $2$.