[前缀和]Tokitsukaze and Strange Inequality Codeforces1678C

Tokitsukaze has a permutation pp of length nn. Recall that a permutation pp of length nn is a sequence p1,p2,…,pnp1,p2,…,pn consisting of nn distinct integers, each of which from 11 to nn (1≤pi≤n1≤pi≤n).

She wants to know how many different indices tuples [a,b,c,d][a,b,c,d] (1≤a<b<c<d≤n1≤a<b<c<d≤n) in this permutation satisfy the following two inequalities:

pa<pcpa<pc and pb>pdpb>pd.

Note that two tuples [a1,b1,c1,d1][a1,b1,c1,d1] and [a2,b2,c2,d2][a2,b2,c2,d2] are considered to be different if a1≠a2a1≠a2 or b1≠b2b1≠b2 or c1≠c2c1≠c2 or d1≠d2d1≠d2.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases. Each test case consists of two lines.

The first line contains a single integer nn (4≤n≤50004≤n≤5000) — the length of permutation pp.

The second line contains nn integers p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n) — the permutation pp.

It is guaranteed that the sum of nn over all test cases does not exceed 50005000.

Output

For each test case, print a single integer — the number of different [a,b,c,d][a,b,c,d] tuples.

Example

input

3

6

5 3 6 1 4 2

4

1 2 3 4

10

5 1 6 2 8 3 4 10 9 7

output

3

0

28

题意： 有一个数组p，求有多少个四元组(a, b, c, d)满足p[a] < p[c] 且 p[b] > p[d]，并且a < b < c < d。

分析： 数组长度比较小，最大只有5000，所以可以想到枚举a和c，然后只需要求出[c+1，n]之间每个d对应的在[a+1, c-1]之间的b的个数。可以维护一个前缀和数组num，num[i][j]表示前i个数中大于j的数有多少个，这样对于确定的区间[a+1, c-1]中满足p[b] > p[d]的个数就是num[c-1][p[d]]-num[a][p[d]]，不过d的位置也是未知的，也需要枚举，时间复杂度就是O(n^3)了，接下来考虑优化掉最内层循环。定义sum[i][j]表示对于[j+1, n]中每个数d在[i+1, j-1]内大于d的b个数之和，这样在枚举完a和c后答案就可以加上sum[a][c]，sum数组的维护可以通过一个简单的区间dp来求得，得到sum数组后这道题目就能够O(n^2)求解了。

还有另外一种简单的方法，维护前i个数中小于j的数字个数pre[i][j]以及后i个数中小于j的数字个数back[i][j]，这样就可以枚举b和c，然后答案叠加pre[b-1][p[c]]*back[c+1][p[b]]。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

int A[5005];
int num[5005][5005];//num[i][j]表示前i个数中有多少个大于a[j]的数 
int sum[5005][5005];//a~c的后缀和 
int sum2[5005];

signed main()
{
	int	T;
	cin >> T;
	while(T--){
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
			scanf("%d", &A[i]);
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++){
				num[j][A[i]] = num[j-1][A[i]]; 
				sum2[j] = 0;
				sum[i][j] = 0;
				if(A[j] > A[i]) num[j][A[i]]++;
			}
		for(int i = 2; i <= n-2; i++)
			for(int j = i+2; j <= n; j++)
				if(A[i] > A[j]) sum2[i]++;
		for(int len = n-1; len >= 3; len--){
			for(int l = 1; l+len-1 <= n-1; l++){
				int r = l+len-1;
				sum[l][r] = sum[l][r+1]-sum2[r]+(num[r-1][A[r+1]]-num[l][A[r+1]]);
			}
		}
		long long ans = 0; 
		for(int a = 1; a+3 <= n; a++){
			for(int c = a+2; c+1 <= n; c++){
				if(A[a] >= A[c]) continue;
				ans += sum[a][c];
			}
		}
		printf("%lld\n", ans);
		
	}
	return 0;
}