Tokitsukaze and Strange Inequality solution codeforces

Tokitsukaze and Strange Inequality solution codeforces

 

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 (1pin1≤pi≤n).

She wants to know how many different indices tuples [a,b,c,d][a,b,c,d] (1a<b<c<dn1≤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 a1a2a1≠a2 or b1b2b1≠b2 or c1c2c1≠c2 or d1d2d1≠d2.

Tokitsukaze and Strange Inequality solution codeforces

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

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

The second line contains nn integers p1,p2,,pnp1,p2,…,pn (1pin1≤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

Tokitsukaze and Strange Inequality solution codeforces

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

Copy
3
0
28

Tokitsukaze and Strange Inequality solution codeforces

In the first test case, there are 33 different [a,b,c,d][a,b,c,d] tuples.

p1=5p1=5p2=3p2=3p3=6p3=6p4=1p4=1, where p1<p3p1<p3 and p2>p4p2>p4 satisfies the inequality, so one of [a,b,c,d][a,b,c,d] tuples is [1,2,3,4][1,2,3,4].

Similarly, other two tuples are [1,2,3,6][1,2,3,6][2,3,5,6][2,3,5,6].

Leave a Comment