A15163. Tokitsukaze and Strange Inequality

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$ .

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$ .

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

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]$ .