记录编号	82566	评测结果	AAAAAAAAAA
题目名称	三元数对	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2013-11-25 19:45:53	内存使用	1.66 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=30001;
int N;
long long a[MAX][2],b[MAX][2],n[MAX][2];
void merge(int l,int r)
{
	if(l>=r)return;
	int mid=(l+r)>>1;
	merge(l,mid);	merge(mid+1,r);
	int temp=l;
	int i=l,j=mid+1;
	while(temp<=r)
	{
		if(a[i][0]<a[j][0]&&i<=mid&&j<=r)
		{
			b[temp][0]=a[i][0];
			b[temp][1]=a[i][1];
			n[a[i][1]][1]+=r-j+1;
			temp++;
			i++;
			continue;
		}
		if(a[i][0]>=a[j][0]&&i<=mid&&j<=r)
		{
			b[temp][0]=a[j][0];
			b[temp][1]=a[j][1];
			n[a[j][1]][0]+=i-l;
			temp++;
			j++;
			continue;
		}
		if(i>mid)
		{
			b[temp][0]=a[j][0];
			b[temp][1]=a[j][1];
			n[a[j][1]][0]+=i-l;
			temp++;
			j++;
			continue;
		}
		if(j>r)
		{
			b[temp][0]=a[i][0];
			b[temp][1]=a[i][1];
			temp++;
			i++;
			continue;
		}
	}
	for(int k=l;k<=r;k++)
	{
		a[k][0]=b[k][0];
		a[k][1]=b[k][1];
	}
}
int main()
{
	freopen("three.in","r",stdin);
	freopen("three.out","w",stdout);
	scanf("%d",&N);
	for(int i=0;i<=N-1;i++)
	{
		scanf("%lld",&a[i][0]);
		a[i][1]=i+1;
	}
	merge(0,N-1);
	long long ans=0;
	for(int i=0;i<=N-1;i++)
		ans+=(n[i][0]*n[i][1]);
	printf("%lld\n",ans);
	return 0;
}