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ţă
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 xi, 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 conţine o singură linie pe care va fi scris un singur număr natural S, reprezentând suma totală minimă pe care o poate plăti televiziunea luptătorilor.
Restricţii
0 < N ≤ 1 000 000
1 ≤ xi ≤ 10 000 pentru orice i număr natural cu proprietatea 1 ≤ i ≤ N
Exemple
k1.in
k1.out
Explicaţii
3
1
1
1
5
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.