中位数定义为所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通常取最中间的两个数值的平均数作为中位数。 

现在有

n个数，每个数都是独一无二的，求出每个数在多少个包含其的区间中是中位数。 

Input多组测试数据 

第一行一个数n(n≤8000)n(n≤8000) 

第二行nn个数，0≤0≤每个数≤109≤109,OutputNN个数，依次表示第ii个数在多少包含其的区间中是中位数。Sample Input

51 2 3 4 5

Sample Output

1 2 3 2 1 解法： 对于每个数字， 从该数字左边开始扫描，统计个数，遇到比它小的+1，比它大的-1，遇到0，答案+1 从该数字右边开始扫描，遇到比它小的-1，比它大的+1,遇到0，答案+1 然后左边右边的差个数相等的，乘起来，加到答案中。 代码：

#include
     
      using namespace std;#include
      
       #include
       
        int a[30000];int cs1[21000],cs2[21000];int main(){	int n;	while(scanf("%d",&n)!=EOF){	for(int i=0;i
        
         =0;j--){		 if(a[j]
         
          a[i]) l2++;else l2--;		 if(l2==0) ans++;		 cs2[l2+n]++;		}		for(int j=0;j<=2*n;j++)			ans+=(long long)cs1[j]*cs2[j];		printf("%lld",ans);		if(i!=n-1) putchar(' ');	}	putchar('\n');	}	return 0;}