Fişierul intrare/ieşire:	permsort.in, permsort.out	Sursă	Lot Botosani 2012 - Baraj 2 Seniori
Autor	Vlad Ionescu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

Cerinta

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

• 1 ≤ n ≤ 1.000.000
• pentru 30% din teste, 1 ≤ n ≤ 5.000

Exemplu

Explicaţie

...

Cum se trimit solutii?