permsort

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 minim din permutare, fie $x$ poziţia sa în cadrul permutării
• 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 $S$ pe $x$.

Astfel, după ce permutarea devine vidă, $S$ va avea o anumită valoare.

Cerință

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 va 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 \leq n \leq 1 \ 000 \ 000$;
• pentru $30\%$ din teste, $1 \leq n \leq 5 \ 000$

Exemplul 1

permsort.in

5
5 4 1 3 2

permsort.out

11

Explicație

În primul exemplu:

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$