這題是看樹狀數組是看到的，博客作者說這個可以用歸并排序，于是就寫了下，發現還好。

對于數組a,歸并排序時的合并階段，分成兩段，也就是(start,mid)和(mid,end)(我這里第一段的下標是從start到mid-1，
第二段的下標是從mid到end-1)。用三個下標分別指向前面一段(i)，后面一段(j)，和新數組下標(idx).那么當出現
num[j] < num[i]的時候，結果就應該加前面一段還沒有進入新數組的數據的長度,比如說當前i = 3；j = 8；mid = 5且
num[8] < num[3]；那么結果應該加上(5-3=2)(記住我的前面一段是到mid-1結束)，因為在這次歸并的過程中要移動(5-3=2)次，
因為(num[3],num[8])是一個逆序對，同時(num[4],num[8])是一個逆序對(似乎這里理解起來有點困難-_-，可以畫一個圖，
自己手動執行下，比如第一個樣例就行（9,1,0,5,4），自己手動執行下，就知道為什么了)。那么這樣的話應該就好做了，
最后一點就是結果會超int用long long或者__int64存
代碼如下(依舊，建議讀者先自己寫)

CODE
 1/**//*
 2 ID:Klion
 3 PROG:POJ_2299
 4 LANG:C++
 5 */
 6#include<iostream>
 7using namespace std;
 8int num[500006];
 9__int64 total;
10void merge(int start,int mid,int end)
11{
12     int tmp[500006];
13     int i = start;
14     int j = mid;
15     int idx = 0;
16     //放到tmp數組里面
17     for(;i < mid && j < end;)
18       {
19         if(num[i] < num[j])
20           {
21                tmp[idx] = num[i];
22                idx++;
23                i++;
24               }
25          else
26              {
27                  tmp[idx] = num[j];
28                  idx++;
29                  j++;
30                  total += (mid-i);
31              }
32       }
33      //把剩下的都放到tmp數組里面去
34          for(;i < mid;i++)
35                {
36                    tmp[idx++] = num[i];
37                }
38       for(;j < end;j++)
39                   {
40                       tmp[idx++] = num[j];
41                   }
42         //把排好序的再賦值到num數組中
43          for(j = start,i = 0;i < idx;i++,j++)
44            num[j] = tmp[i]; 
45}
46void merge_sort(int start,int end)
47{
48      if(start + 1 == end)
49          {
50              return;
51          }
52      int mid = (start + end) >> 1;
53      merge_sort(start,mid);
54      merge_sort(mid,end);
55      merge(start,mid,end);
56}
57int main(void)
58{
59      freopen("2299.in","r",stdin);
60      freopen("2299.out","w",stdout);
61      int n;
62      while(scanf("%d",&n),n)
63        {
64            total = 0;
65            for(int i = 0;i < n;i++)
66              {
67                  scanf("%d",&num[i]);
68              } 
69            merge_sort(0,n);
70            printf("%I64d\n",total);
71        }
72    return 0;
73}
74