A16575 | $Unique Median$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

如果一个长度为 $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$ 中“好”子数组的数量。 $^*$ 数组 $x$ 是数组 $y$ 的子数组，若 $x$ 可以通过从 $y$ 的开头删除若干（可能为零或全部）元素，并从末尾删除若干（可能为零或全部）元素得到。

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

C++ 编辑器

输入

输出