← 返回题目列表

Codeforces · 1462/E1

E1. 关闭元组(简单版)

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

这是这个问题的简单版本。简单版本和困难版本之间的唯一区别是对 $$$k$$$ 和 $$$m$$$ 的约束(在此版本中 $$$k=2$$$ 和 $$$m=3$$$)。另外,在这个版本的问题中,您不需要按模输出答案。

给定一个序列 $$$a$$$,长度为 $$$n$$$,由从 $$$1$$$ 到 $$$n$$$ 的整数组成。该序列可能包含重复项(即某些元素可以相等)。

查找 $$$m = 3$$$ 元素的元组数量,使得元组中的最大数量与最小数量相差不超过 $$$k = 2$$$。形式上,您需要找到索引 $$$i < j < z$$$ 的三元组的数量,使得

$$$$$$\max(a_i, a_j, a_z) - \min(a_i, a_j, a_z) \le 2.$$$$$$

例如,如果 $$$n=4$$$ 和 $$$a=[1,2,4,3]$$$,则有两个这样的三元组($$$i=1, j=2, z=4$$$ 和 $$$i=2, j=3, z=4$$$)。如果 $$$n=4$$$ 且 $$$a=[1,1,1,1]$$$,则所有四个可能的三元组都是合适的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列 $$$a$$$ 的长度。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 序列 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

输出给定测试用例的 $$$t$$$ 答案。每个答案都是所需数量的元素三元组,使得三元组中的最大值与最小值的差异不超过$$$2$$$。请注意,与问题的困难版本不同,您不需要按模输出答案。您必须输出答案的精确值。

示例

输入 #1

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

输出 #1

2
4
0
15