1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<stack> 7 #include<math.h> 8 using namespace std; 9 typedef long long LL;10 int bitl[200005];11 int bitr[200005];12 int lowbit(int x);13 void addl(int x);14 void addr(int x);15 int  askl(int x);16 int askr(int x);17 int ans[100005];18 int bns[100005];19 int aksl[200005];20 int aksr[200005];21 int main(void)22 {23         int T;24         scanf("%d",&T);25         while(T--)26         {27                 int n;28                 scanf("%d",&n);29                 memset(bitl,0,sizeof(bitl));30                 memset(bitr,0,sizeof(bitr));31                 int i,j;32                 for(i = 1; i <= n; i++)33                 {34                         scanf("%d",&ans[i]);35                 }36                 int cn = 1;37                 for(i = n; i >= 1; i--)38                 {39                         bns[cn++] = ans[i];40                 }41                 for(i = 1; i <= n; i++)42                 {43                     aksl[i] = askl(ans[i]-1);44                     addl(ans[i]);45                     aksr[i] = askr(bns[i]-1);46                     addr(bns[i]);47                 }48                 LL sum = 0;49                 for(i = 2;i <= n-1;i++)50                 {51                     sum = sum + (LL)aksl[i]*(LL)(n-i-aksr[n-i+1])+(LL)(i - 1 - aksl[i])*(LL)aksr[n-i+1];52                 }53                 printf("%lld\n",sum);54         }55         return 0;56 }57 int lowbit(int x)58 {59         return x&(-x);60 }61 void addl(int x)62 {63         while(x <= 100000)64         {65                 bitl[x]++;66                 x += lowbit(x);67         }68 }69 void addr(int x)70 {71         while(x <= 100000)72         {73                 bitr[x]++;74                 x += lowbit(x);75         }76 }77 int  askl(int x)78 {79         int sum = 0;80         while(x > 0)81         {82                 sum += bitl[x];83                 x -= lowbit(x);84         }85         return sum;86 }87 int askr(int x)88 {89         int sum = 0;90         while(x > 0)91         {92                 sum += bitr[x];93                 x -= lowbit(x);94         }95         return sum;96 }