k1

Time limit: 0.45s Memory limit: 32MB Input: k1.in Output: k1.out

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 NN 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 NN, reprezentând numărul de luptători invitaţi la turneu, iar pe următoarele NN linii se află câte un număr natural nenul xix_i, reprezentând rating-ul iniţial al celui de-al ii-lea luptător.

Date de ieșire

Fişierul de ieşire k1.out conţine un singur număr natural ss, reprezentând suma totală minimă pe care o poate plăti televiziunea luptătorilor.

Restricții și precizări

  • 1N1 000 0001 \leq N \leq 1 \ 000 \ 000;
  • 1xi10 0001 \leq x_i \leq 10 \ 000

Exemplu

k1.in

3
1
1
1

k1.out

5

Explicație

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

Log in or sign up to be able to send submissions!