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

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}

Tokitsukaze and Strange Inequality solution codeforces

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

Output

For each test case, print a single integer — the number of different $[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 $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]$ .

Tokitsukaze and Strange Inequality solution codeforces

Tokitsukaze and Strange Inequality solution codeforces

Tokitsukaze and Strange Inequality solution codeforces

Tokitsukaze and Strange Inequality solution codeforces

Leave a Comment Cancel reply