← 返回题目列表

Codeforces · 1677/A

A. 时风和奇怪的不平等

中文机器翻译题面 查看原题

Tokitsukaze 的排列 $$$p$$$ 长度为 $$$n$$$。回想一下,长度为 $$$n$$$ 的排列 $$$p$$$ 是一个序列 $$$p_1, p_2, \ldots, p_n$$$,由 $$$n$$$ 个不同的整数组成,每个整数从 $$$1$$$ 到 $$$n$$$ ($$$1 \leq p_i \leq n$$$)。

她想知道这个排列中有多少个不同的索引元组 $$$[a,b,c,d]$$$ ($$$1 \leq a < b < c < d \leq n$$$) 满足以下两个不等式:

$$$p_a < p_c$$$ 和 $$$p_b > p_d$$$。

请注意,如果 $$$a_1 \ne a_2$$$ 或 $$$b_1 \ne b_2$$$ 或 $$$c_1 \ne c_2$$$ 或 $$$c_1 \ne c_2$$$ 或$$$d_1 \ne d_2$$$。

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 不同 $$$[a,b,c,d]$$$ 元组的数量。

示例

输入 #1

3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7

输出 #1

3
0
28

注意

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

$$$p_1 = 5$$$、$$$p_2 = 3$$$、$$$p_3 = 6$$$、$$$p_4 = 1$$$,其中 $$$p_1 < p_3$$$ 且 $$$p_2 > p_4$$$ 满足不等式,因此 $$$[a,b,c,d]$$$ 之一元组是$$$[1,2,3,4]$$$。

类似地,其他两个元组是$$$[1,2,3,6]$$$,$$$[2,3,5,6]$$$。