如果 $$$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$$$,它们不相等。