TopCoder

User's AC Ratio

95.7% (44/46)

Submission's AC Ratio

67.4% (64/95)

Tags

Description

給你一列共 n 個數字的數列:

a1, a2, a3, a4, ... an

如果某個在左邊的數 x 大於某個在他在他右邊的數 y,那這樣的 (x,y) 就稱為一個逆序數對。

給你這個數列,請輸出有幾個逆序數對。

請注意要嚴格大於才算喔,等於不算。

Input Format

本題有多組測試資料
每組測試資料先有一個 n 代表有幾個數字,
接下來有一列共 n 個數代表這個數列 a1, a2, a3 ... an。

n 最多不超過 100。

Output Format

對於每組測資,請印出有幾個逆序數對。

Sample Input

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

Sample Output

3
6
0

Hints

舉例來說,若數列是 3,1,4,1,則逆序數對有:
(3,1), (3,1), (4,1)

共 3 個。

Problem Source

原TIOJ1667 / kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144