Fișierul intrare/ieșire	inversiuni.in, inversiuni.out	Sursă	Shumen Juniori 2013
Autor	Stoyan Kapralov	Adăugată de	Radu Muntean • heracle
Timp de execuție pe test	0.5 sec	Limită de memorie	9000 KB
Scorul tău	N/A	Dificultate	3.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Inversiuni

O permutare de ordin n este o secvență de n numere : a{₁}, a2, a3, ..., an, în care fiecare număr de la 1 la n apare o singură dată.

Două numere dintr-o permutare, ai si aj, formeaza o inversiune daca ai > aj si i < j ;

De exemplu, in permutarea 4 2 7 1 5 6 3, exista in total 10 inversiuni intre numerele de pe pozitiile : 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3;

Cerinta

Scrieti un program care sa afiseze numarul total de inversiuni la o permutare data;

Date de intrare (in fisierul “inversiuni.in” )

Pe prima linie se va afla valoarea lui n, iar pe a doua linie cele n numere (delimitate prin spatiu) care formeaza permutarea.

Date de ieșire (in fisierul “inversiuni.out” )

Se va afisa un singur numar care prezinta numarul total de inversiuni a permutarii date.

Restricții

2 ≤ n ≤ 1000000

Exemplu