CF2056D.Unique Median

An array $b$ of $m$ integers is called good if, when it is sorted, $b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}$. In other words, $b$ is good if both of its medians are equal. In particular, $\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil$ when $m$ is odd, so $b$ is guaranteed to be good if it has an odd length.

You are given an array $a$ of $n$ integers. Calculate the number of good subarrays$^{\text{∗}}$ in $a$.

$^{\text{∗}}$An array $x$ is a subarray of an array $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

一个包含 $m$ 个整数的数组 $b$ 被称为好数组，当且仅当将其排序后满足

$$b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}.$$

换言之，$b$ 是好数组当且仅当它的两个中位数相等。特别地，当 $m$ 为奇数时，恒有

$$\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil,$$

因此所有长度为奇数的数组必定是好数组。

给定一个包含 $n$ 个整数的数组 $a$，请计算 $a$ 中好子数组$^{\text{∗}}$ 的数量。

$^{\text{∗}}$ 数组 $x$ 是数组 $y$ 的子数组，当且仅当 $x$ 可通过从 $y$ 的开头删除若干（可能为零个或全部）元素、并从 $y$ 的末尾删除若干（可能为零个或全部）元素而得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le \color{red}{\textbf{10}}$) — the given array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer representing the number of good subarrays in $a$.

对于每个测试用例，输出一个整数，表示数组 $a$ 中“好”子数组的个数。

In the first case, every subarray is good since all its elements are equal to $1$.

In the second case, an example of a good subarray is $b = [10, 2, 3, 3]$. When it is sorted, $b = [2, 3, 3, 10]$, so $b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$. Another example would be $b = [1, 10, 2]$. On the other hand, $b = [1, 10]$ is not good as its two medians are $1$ and $10$, which are not equal.

第一种情况中，每个子数组都是“好”的，因为其所有元素都等于 $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$，二者不相等。