|
|
 #include <iostream>
using namespace std;
const int M=20000+5;
const int Maxn=100000+5;
int skill[M];
int tree[Maxn];
int lmax[M],lmin[M];
int rmax[M],rmin[M];
  int lowbit(int t) {return t&(-t);}
void add(int i)
{
 while(i<Maxn)
  {
tree[i]++;
i+=lowbit(i);
 }
 }
int sum(int i)
{
int tot=0;
while(i>0)
{
tot+=tree[i];
i-=lowbit(i);
}
return tot;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&skill[i]);
memset(tree,0,sizeof(tree));
for(i=1;i<=n;i++)
{
lmin[i]=sum(skill[i]);
lmax[i]=i-lmin[i]-1;
add(skill[i]);
}
memset(tree,0,sizeof(tree));
for(i=n;i>=1;i--)
{
rmin[i]=sum(skill[i]);
rmax[i]=sum(Maxn)-rmin[i];
add(skill[i]);
}
__int64 ans=0;
for(i=1;i<=n;i++)
ans+=lmax[i]*rmin[i]+lmin[i]*rmax[i];
printf("%I64d\n",ans);
}
return 0;
}
|