题意：给你一个长度为n的全排列，求有多少组（x，y，z）满足，x<y<z，且a【x】<a【z】<a【y】。
先求出满足，a【x】<a【z】，a【x】<a【y】有多少组，
对于当前点，后面有k个数比他大，那么有 k*（k-1）/2组。
我们在减去 a【x】<a【y】<a【z】的情况。
对于当前点，前面有k个数比他小，后面有u个数比他大，那么就有 k*u组。
利用树状数组来维护。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN=100000+5;
const int mod=100000007;
int n;
int c[MAXN],a[MAXN];//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
int num[MAXN];
int lowbit(int i)
{return i&(-i);
}
int sum(int x){int sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}
void add(int x, int val){while(x <= n){c[x] += val;x += lowbit(x);}
}
int main()
{int t;scanf("%d",&t);int k=0;while(t--){k++;scanf("%d",&n);memset(c,0,sizeof(c));memset(num,0,sizeof(num));ll sum1=0;ll sum2=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);num[a[i]]=sum(a[i]-1);ll t=n-a[i]+num[a[i]]+1-i;//cout<<a[i]<<" "<<t<<endl;sum1+=(t*(t-1)/2);add(a[i],1);if(i==1||i==n) continue;sum2+=((n-a[i]-i+num[a[i]]+1)*num[a[i]]);}ll ans=(sum1-sum2)%mod;printf("Case #%d: ",k);printf("%lld\n",ans);}return 0;
}