题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5775
题目大意：
冒泡排序的规则如下，一开始给定1~n的一个排列，求每个数字在排序过程中出现的最远端位置的差。
for(int i=1;i<=N;++i)
for(int j=N,t;j>i;—j)
if(P[j-1] > P[j])
t=P[j],P[j]=P[j-1],P[j-1]=t;
题目思路：
【归并排序】【逆序数】
首先，一个数左移次数和右移次数时确定的（左边比它大的个数和右边比它小的个数）
根据规则，每一次都是找第i小的数交换到位置i上，所以一个数只会往左一次，不存在先往左移动再往右移动再往左移动。
所以一个数最远端位置差就为这两个数的最大值。
那么可以先通过归并排序求出一个数右边比它小的数的个数ai，通过计算就知道左边比它大的个数，然后取max。
//
//by coolxxx
//
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define eps (1e-8)
#define J 10000000
#define MAX 0x7f7f7f7f
#define PI 3.1415926535897
#define N 100004
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
int p[N],a[N],b[N],le[N],ri[N],num[N];
void merge(int s[],int l,int mid,int r)
{
int i,j,k,n1=mid-l+,n2=r-mid;
for(i=;i<=n1;i++)le[i]=s[l+i-];
for(i=;i<=n2;i++)ri[i]=s[mid+i];
le[n1+]=ri[n2+]=MAX;
for(i=j=,k=l;k<=r;k++)
{
if(le[i]<=ri[j])
s[k]=le[i++];
else
s[k]=ri[j++],b[s[k]]+=n1-i+;
}
}
void mergesort(int s[],int l,int r)
{
int mid=(l+r)>>;
if(l<r)
{
mergesort(s,l,mid);
mergesort(s,mid+,r);
merge(s,l,mid,r);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j;
// for(scanf("%d",&cas);cas;cas--)
for(scanf("%d",&cas),cass=;cass<=cas;cass++)
// while(~scanf("%s",s))
// while(~scanf("%d",&n))
{
memset(b,,sizeof(num));
printf("Case #%d: ",cass);
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&num[i]);
p[num[i]]=i;
}
mergesort(num,,n);
for(i=;i<=n;i++)
a[i]=b[i]+i-p[i];
for(i=;i<=n;i++)
printf("%d%c",max(a[i],b[i]),i==n?'\n':' ');
}
return ;
}
/*
// //
*/