TopCoder

User's AC Ratio

95.4% (62/65)

Submission's AC Ratio

60.1% (83/138)

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

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1