10923 - Inversion Pair   

Description

在一個N個數字的序列S裡,當S[i] > S[j] 且 i < j的時候,我們說(i ,j)是一個逆序數對。

Hint : 利用歸併排序法計算一個序列裡有多少逆序數對。

Hint : 思考一下在merge的過程,怎麼找到答案!

Hint : 直接使用兩層迴圈來找答案的話會超過系統時間限制。

Input

只有一筆測資,第一行為一個數字N,代表接下來有N行,每行有一個數字。這N個數字都會相異。

數字範圍:

0 < N < 20000

Output

輸出逆序數對的個數。

Sample Input  Download

Sample Output  Download

Tags

2 0 韩永楷老师数据结构mooc MOOC



Discuss