40008. Practice 8: 逆序數對

I'm a slow walker, but I never walk backwards.

給你一個正整數序列$a_0, a_1,\cdots, a_{N-1}$,請計算這個序列的「逆序數對」數量。所謂逆序數對數量,指的是符合$0\leq i\lt j\lt N$且$a_i>a_j$的相異$(i,j)$組數。

Input/Output

輸入的第一行有一個正整數$T$,代表測資數量。 接下來每兩行代表一組測資。第一行有一個正整數$N$,代表序列長度;第二行有$N$個正整數$a_i$,代表給定的序列。

請對每筆測資輸出一行,代表逆序數對數量。

Subtasks/Constraints

所有測資皆符合: $T\leq 10; N\leq 10^ 6; a_i \leq 10^ 9$

  1. $N\leq 2$ (5 pts)
  2. $a_i \leq 2$ (15 pts)
  3. $N\leq 5000, a_i \leq 10$ (10 pts)
  4. $N\leq 500$ (10 pts)
  5. $N\leq 5000$ (10 pts)
  6. 保證答案不超過$2\times 10^ 7$ (10 pts)
  7. 無額外限制 (40 pts)

Sample Input

2
5
5 4 3 2 1
5
1 2 3 5 4

Sample Output

10
1

Discussion