[Solution] Tokitsukaze and Strange Inequality solution codeforces

Tokitsukaze and Strange Inequality solution codeforces – Tokitsukaze has a permutation $p$ of length $n$ . Recall that a permutation $p$ of length $n$ is a sequence $p_{1}, p_{2}, \dots, p_{n}$ consisting of $n$ distinct integers, each of which from $1$ to $n$ ( $1 \leq p_{i} \leq n$ ).

[Solution] Tokitsukaze and Strange Inequality solution codeforces

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} \neq a_{2}

b_{1} \neq b_{2}

c_{1} \neq c_{2}

d_{1} \neq 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}, \dots, 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$ .