Zliczanie inwersji

Limit czasu: 0.5s | Limit pamięci: 64MB

Inwersją nazywamy parę $(i,j)$ taką, że $i < j$ i $a_i > a_j$. Znajdź liczbę inwersji dla zadanego ciągu liczb $a_1, a_2, \ldots, a_n$.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara liczbę inwersji ciągu elementów $a_i$.

Ograniczenia

• $1 \le n \le 200 000$
• $0 \le a_i \le 10^9$
• liczby $a_i$ są parami różne

Przykłady

Wejście 1

5
3 5 2 1 4

Wyjście 1

6

Wejście 2

3
3 1 2

Wyjście 2

2