1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 20005 6 #define lson l, mid, rt<<1 7 #define rson mid+1, r, rt<<1|1 8  9 int buf[MAXN], bk[MAXN];10 int sum[MAXN<<2], n;11 12 int comp(const void *a, const void *b) {13     return *(int *)a - *(int *)b;14 }15 16 void PushUP(int rt) {17     sum[rt] = sum[rt<<1] + sum[rt<<1|1];18 }19 20 void build(int l, int r, int rt) {21     sum[rt] = 0;22     if (l == r)23         return ;24     int mid = (l+r)>>1;25     build(lson);26     build(rson);27 }28 29 int query(int ll, int rr , int l, int r, int rt) {30     if (ll<=l && r<=rr)31         return sum[rt];32     int mid = (l+r)>>1;33     int ret = 0;34     if (ll <= mid)35         ret += query(ll, rr, lson);36     if (rr > mid)37         ret += query(ll, rr, rson);38     return ret;39 }40 41 void update(int x, int l, int r, int rt) {42     if (l == r) {43         ++sum[rt];44         return ;45     }46     int mid = (l+r)>>1;47     if (x <= mid)48         update(x, lson);49     else50         update(x, rson);51     PushUP(rt);52 }53 54 int getIndex(int x) {55     int l=1, r=n, mid;56 57     while (l <= r) {58         mid = (l+r)>>1;59         if (bk[mid] == x)60             return mid;61         if (x > bk[mid])62             l = mid + 1;63         else64             r = mid - 1;65     }66     return 0;67 }68 69 int main() {70     int t;71     int i;72     int index;73     __int64 ll, lg, rl, rg;74     __int64 ans;75 76     scanf("%d", &t);77     while (t--) {78         scanf("%d", &n);79         for (i=1; i<=n; ++i) {80             scanf("%d", &buf[i]);81             bk[i] = buf[i];82         }83         build(1, n, 1);84         qsort(bk+1, n, sizeof(int), comp);85         ans = 0;86         for (i=1; i<=n; ++i) {87             index = getIndex(buf[i]);88             ll = query(1, index, 1, n, 1);89             lg = i-1-ll;90             rl = index-1-ll;91             rg = n-index-lg;92             ans += ll*rg + lg*rl;93             update(index, 1, n ,1);94         }95         printf("%I64d\n", ans);96     }97 98     return 0;99 }