Zadanie ASD4
Treść
Wyznacz liczbę inwersji w tablicy w czasie O(nlgn)
Specyfikacja wejścia
W pierwszej linii wejścia znajduje się liczba D oznaczająca liczbę
zestawów, które za chwile pojawią się na wejściu.
Każdy zestaw składa się najpierw z liczby N oznaczającej długość tablicy
(1<=N<=100.000), a po niej N
elementów tej tablicy, wszystkie nie mniejsze niż
-2.000.000.000, nie większe niż 2.000.000.000, wszystkie różne.
Specyfikacja wyjścia
Dla każdego zestawu należy w osobnej linii zapisać jedną liczbę
oznaczającą liczbę inwersji w tablicy
Przykład
Wejście
2
3 2 4 5
4 9 0 3 8
Wyjście
0
3