CF1677A.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 \lt b \lt c \lt d \leq n$) in this permutation satisfy the following two inequalities:

$p_a \lt p_c$ and $p_b \gt 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$.

Tokitsukaze 有一个长度为 $n$ 的排列 $p$。回忆一下，长度为 $n$ 的排列 $p$ 是一个由 $n$ 个互不相同的整数组成的序列 $p_1, p_2, \ldots, p_n$，其中每个数均在 $1$ 到 $n$ 之间（即 $1 \leq p_i \leq n$）。

她想知道，在该排列中，有多少个不同的下标四元组 $[a,b,c,d]$（满足 $1 \leq a \lt b \lt c \lt d \leq n$）使得以下两个不等式同时成立：

$p_a \lt p_c$ 且 $p_b \gt p_d$。

注意：若两个四元组 $[a_1,b_1,c_1,d_1]$ 与 $[a_2,b_2,c_2,d_2]$ 满足 $a_1 \ne a_2$ 或 $b_1 \ne b_2$ 或 $c_1 \ne c_2$ 或 $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$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。每个测试用例由两行组成。

第一行包含一个整数 $n$（$4 \leq n \leq 5000$），表示排列 $p$ 的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示排列 $p$。

保证所有测试用例的 $n$ 之和不超过 $5000$。

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

对于每个测试用例，输出一个整数——不同的 $[a,b,c,d]$ 元组的个数。

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 \lt p_3$ and $p_2 \gt 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]$.

在第一个测试用例中，共有 $3$ 个不同的 $[a,b,c,d]$ 元组。

$p_1 = 5$，$p_2 = 3$，$p_3 = 6$，$p_4 = 1$，其中 $p_1 \lt p_3$ 且 $p_2 \gt p_4$ 满足该不等式，因此其中一个 $[a,b,c,d]$ 元组为 $[1,2,3,4]$。

类似地，另外两个元组分别为 $[1,2,3,6]$ 和 $[2,3,5,6]$。