TCIRC：https://judge.tcirc.tw/ShowProblem?problemid=d064
考慮一個數列 A[1:n]。如果 A 中兩個數字 A[i] 和 A[j] 滿足 i<j AND A[j]<A[i]，也就是在前面的比較大，則我們說 (A[i],A[j]) 是一個反序對 (inversion)。
定義 W(A)為數列 A 中反序對數量。例如，在數列 A=(3,1,9,8,9,2) 中，一共有(3,1)、(3,2)、(9,8)、(9,2)、(8,2)、(9,2) 一共 6 個反序對，所以 W(A)=6。
請注意到序列中有兩個 9 都在 2 之前，因此有兩個(9,2)反序對，也就是說，不同位置的反序對都要計算，不管兩對的內容是否一樣。 請撰寫一個程式，計算一個數列 A 的反序數量 W(A)。
輸入說明
第一行是一個正整數 n ，代表數列長度， 第二行有 n 個非負整數，是依序數列內容，數字間以空白隔開。 n 不超過 1e5 數列內容不超過 1e6 。
輸出說明
輸出反序對數量。
輸入範例1
6
3 1 9 8 9 2
輸出範例1
6
解題策略
分而治之
方法一：計算出中間值，分割出比中間值大的陣列與比中間值小的陣列
方法二：修改mergesort，當右半陣列元素merge到tmp陣列時，左半部剩餘元素個數就是逆序個數，累加這些個數就是答案
方法一
方法二