Pentru a diminua efectele crizei economice prin creşterea numărului de telespectatori (şi implicit a veniturilor provenite din publicitate), redacţia „Şocuri şi concursuri” a unei televiziuni selecte a decis să organizeze un turneu de lupte k1. La acesta vor lua parte N sportivi. Fiecare dintre aceştia are un rating, calculat pe baza rezultatelor sale anterioare. Suma de bani pe care o primeşte pentru fiecare luptă la care va lua parte este egală cu acest rating. În urma fiecărei lupte rating-ul învingătorului creşte cu valoarea rating-ului învinsului.

Cerința

Cum televiziunea îşi doreşte un profit cât mai mare, conducătorii acesteia doresc să programeze meciurile astfel încât să plătească luptătorilor o sumă totală cât mai mică. Ştiind că nu există lupte încheiate la egalitate şi că turneul se termină doar după ce a fost stabilit un învingător, stabiliţi care este suma totală minimă pe care o pot plăti organizatorii. Suma totală plătită de televiziune este obţinută prin adunarea sumelor plătite tuturor luptătorilor pe parcursul turneului.

Date de intrare

Fișierul de intrare k1.in conține pe prima linie o valoare N, reprezentând numărul de luptători invitaţi la turneu, iar pe următoarele N linii se află câte un număr natural nenul x[i], reprezentând rating-ul iniţial al celui de-al i-lea luptător.

Date de ieșire

Fișierul de ieșire k1.out va conține pe prima linie un singur număr natural s, reprezentând suma totală minimă pe care o poate plăti televiziunea luptătorilor.

Restricții și precizări

• 0 < N ≤ 1 000 000
• 1 ≤ xi ≤ 10 000 pentru orice i număr natural cu proprietatea 1 ≤ i ≤ N

Exemplu:

k1.in

3
1
1
1

k1.out

5

Explicație

La prima luptă participă 2 sportivi având fiecare rating-ul 1. În ultimul meci se vor întâlni un luptător cu rating-ul 2 (învingătorul primului meci) şi altul cu rating 1 (cel care nu a participat la prima luptă). Învingătorul primului meci primeşte în total 3 (1 pentru prima luptă şi 2 pentru cea de a doua), cel care a pierdut prima luptă şi cel care a participat doar la ultima primesc câte 1, deci televiziunea va plăti în total 5.