#include <stdio.h>
#define MAXN 500000
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int height[MAXN+1],temp[MAXN+1];
__int64 sum;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void merge(int *a,int l,int mid,int r)
{
int i,j,k;
i=0,j=l,k=mid;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(j<mid &&k <r)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a[j]>a[k])
{
sum += mid-j;
temp[i++] = a[k++];
}
else temp[i++] = a[j++];
}
while(j<mid)
temp[i++] = a[j++];
while(k<r)
temp[i++] = a[k++];
for(i=0; i<r-l; i++) a[l+i] = temp[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void divide(int *a,int l,int r)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(l+1<r)
{
int mid = (l+r)>>1;
divide(a,l,mid);
divide(a,mid,r);
merge(a,l,mid,r);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int n,i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d",&n)&&n)
{
for(i=sum=0; i<n; i++) scanf("%d",&height[i]);
divide(height,0,n);
printf("%I64d\n",sum);
}
}