A121003.小枫的排列谜题

小枫、小午和小安三个人在玩一个数字推理游戏。

小枫在黑板上写下一个长度为 $n$ 的排列 $p$。
（排列是指 $1$ 到 $n$ 每个整数恰好出现一次的序列。）

小午需要从排列中选出四个位置 $a, b, c, d$，要求：

• $1 \le a < b < c < d \le n$
• $p_a < p_c$ 且 $p_b > p_d$

小安则负责记录小午一共能找出多少个不同的四元组 $(a, b, c, d)$。
两个四元组不同，当且仅当至少有一个位置的下标不同。

小午觉得这个游戏有点难，你能帮他算一算吗？

第一行一个整数 $t$——测试用例的数量。

每个测试用例包含两行：

• 第一行一个整数 $n$——排列的长度。
• 第二行 $n$ 个整数 $p_1, p_2, \ldots, p_n$——表示排列 $p$。

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

对于每个测试用例，输出一个整数，表示满足条件的四元组总数。

数据范围

对于 $100\%$ 的测试数据，满足：$1 \le t \le 1000$，$4 \le n \le 5000$，$1 \le p_i \le n$ 。