← 返回题目列表

Codeforces · 2056/D

D. 唯一中位数

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

如果 $$$b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}$$$,则 $$$m$$$ 整数的数组 $$$b$$$ 被称为良好。换句话说,如果 $$$b$$$ 的两个中位数相等,则 $$$b$$$ 是好的。特别是,当 $$$m$$$ 为奇数时, $$$\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil$$$ 是奇数,因此如果 $$$b$$$ 的长度为奇数,则保证是好的。

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。计算$$$a$$$中的好子数组$$$^{\text{*}}$$$的数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le \color{red}{\textbf{10}}$$$) - 给定数组。

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

输出

对于每个测试用例,输出一个整数,表示 $$$a$$$ 中良好子数组的数量。

示例

输入 #1

3
4
1 1 1 1
5
1 10 2 3 3
10
6 3 2 3 5 3 4 2 3 5

输出 #1

10
11
42

注意

在第一种情况下,每个子数组都很好,因为它的所有元素都等于 $$$1$$$。

在第二种情况下,一个好的子数组的例子是 $$$b = [10, 2, 3, 3]$$$。排序后,$$$b = [2, 3, 3, 10]$$$,所以$$$b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$$$。另一个例子是 $$$b = [1, 10, 2]$$$。另一方面,$$$b = [1, 10]$$$ 不好,因为它的两个中位数是 $$$1$$$ 和 $$$10$$$,它们不相等。