Tokitsukaze and Strange Inequality

1000ms

262144K

Description:

Tokitsukaze has a permutation $$$p$$$ of length $$$n$$$. Recall that a permutation $$$p$$$ of length $$$n$$$ is a sequence $$$p_1, p_2, \ldots, p_n$$$ consisting of $$$n$$$ distinct integers, each of which from $$$1$$$ to $$$n$$$ ($$$1 \leq p_i \leq n$$$).

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

$$$p_a < p_c$$$ and $$$p_b > p_d$$$.

Note that two tuples $$$[a_1,b_1,c_1,d_1]$$$ and $$$[a_2,b_2,c_2,d_2]$$$ are considered to be different if $$$a_1 \ne a_2$$$ or $$$b_1 \ne b_2$$$ or $$$c_1 \ne c_2$$$ or $$$d_1 \ne d_2$$$.

Input:

The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Each test case consists of two lines.

The first line contains a single integer $$$n$$$ ($$$4 \leq n \leq 5000$$$) — the length of permutation $$$p$$$.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output:

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

Sample 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

Sample Output:

3
0
28

Note:

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

$$$p_1 = 5$$$, $$$p_2 = 3$$$, $$$p_3 = 6$$$, $$$p_4 = 1$$$, where $$$p_1 < p_3$$$ and $$$p_2 > p_4$$$ satisfies the inequality, so one of $$$[a,b,c,d]$$$ tuples is $$$[1,2,3,4]$$$.

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

Informação

Provedor Codeforces

Código CF1677A