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₁, a₂, a₃, ..., a_n, în care fiecare număr de la 1 la n apare o singură dată.

Două numere dintr-o permutare, a_i și a_j, formează o inversiune dacă a_i > a_j și i < j.

De exemplu, în permutarea 4 2 7 1 5 6 3, există in total 10 inversiuni între numerele de pe pozițiile : 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Cerință

Scrieți un program care să afișeze numărul total de inversiuni ale unei permutări date.

Date de intrare

Pe prima linie a fișierului inversiuni.in se va afla valoarea lui n, iar pe a doua linie cele n numere (delimitate prin spațiu) care formeaza permutarea.

Date de ieșire

În fișierul inversiuni.out veți afișa un singur număr, anume numărul total de inversiuni ale permutării date la intrare.

Restricții

• 2 ≤ n ≤ 1 000 000

Exemplu