Pracsiu Dan (dnprx) Grădinarul Marian are la dispoziţie o permutare cu n elemente şi un număr natural S care iniţial are valoarea 0. Marian execută n operaţii de forma:
- alege elementul poziția
xa minimului din permutare - elimină acest element din permutare, iar toate elementele de la stânga sa le mută la sfârşitul permutării (păstrând ordinea elementelor din stânga)
- adună la
Spex.
Astfel, după ce permutarea devine vidă, S va avea o anumită valoare.
Cerința
Determinaţi valoarea lui S după ce grădinarul Marian termină de executat toate cele n operaţii.
Date de intrare
Fișierul de intrare permsort.in conține pe prima linie un număr natural n, reprezentând numărul de elemente ale permutării, iar pe a doua linie n numere naturale distincte cuprinse între 1 şi n, separate prin câte un spaţiu, reprezentând permutarea asupra căreia Marian aplică operaţiile.
Date de ieșire
Fișierul de ieșire permsort.out va conține pe prima linie un număr natural reprezentând valoarea lui S după execuţia celor n operaţii.
Restricții și precizări
1 ≤ n ≤ 1.000.000- • pentru 30% din teste,
1 ≤ n ≤ 5.000
Exemplul 1:
permsort.in
5 5 4 1 3 2
permsort.out
11
Explicație
1) Elementul minim din permutare este 1 şi se află pe poziţia 3. După acest pas, S devine 0 + 3 = 3, iar permutarea rămâne (elementele din stânga lui 1 se mută în aceeaşi ordine la sfârşit): (3 2 5 4).
2)Elementul minim din permutare este 2 şi se află pe poziţia 2. După acest pas, S devine 3 + 2 = 5, iar permutarea rămâne: (5 4 3).
3)Elementul minim din permutare este 3 şi se află pe poziţia 3. După acest pas, S devine 5 + 3 = 8, iar permutarea rămâne: (5 4).
4)Elementul minim din permutare este 4 şi se află pe poziţia 2. După acest pas, S devine 8 + 2 = 10, iar permutarea rămâne: (5).
5)Elementul minim din permutare este 5 şi se află pe poziţia 1. După acest pas, S devine 10 + 1 = 11, iar permutarea devine vidă.
Valoarea finală a lui S este 11.
Exemplul 2:
permsort.in
7 7 5 6 3 1 2 4
permsort.out
16
Explicație
S = 5 + 1 + 5 + 1 + 2 + 1 + 1