TopCoder

User's AC Ratio

73.7% (115/156)

Submission's AC Ratio

21.4% (215/1005)

Tags

Description

對一個數列S來說,若S的第i項si與第j項sj符合si>sj,並且i<j的話,那麼我們說(i,j)是一個逆序數對。請問給定S,總共有多少個逆序數對呢?

Input Format

輸入檔可能包含多筆測試資料,每筆測試資料第一列會有一個正整數 n(1<=n<=100,000),第二列有n個整數依序為數列S的每一項,以一個空白隔開。當n=0的時候代表輸入結束,你不必對這筆資料作處理。所有數字都可以用有號32-bit整數型態儲存。

Output Format

對於每組測試資料請先輸出這是第幾個序列,然後是該序列的逆序數對的總數。請參考Sample Output。

Sample Input

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

Sample Output

Case #1: 0
Case #2: 1

Hints

註:請盡量不要使用cin處理輸入,否則極有可能會TLE。

Problem Source

原TIOJ1080 / 經典問題練習。Problem Setter: Tmt。

Subtasks

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