解题思路

先把题意重新整理一下。

对于某个值 $x$，假设它在数组中的出现位置依次为

题目内容

给定一个长度为 $n$ 的数组 $\{a_1, a_2, \dots, a_n\}$。我们称一对下标 $(i, j)$ 为相邻等值对，当且仅当 $1 \leq i < j \leq n$，$a_i = a_j$，并且对于任意 $i <k < j$，都有 $a_k \neq a_i$。

对每一个相邻等值对 $(i, j)$，定义其贡献为区间 $[i, j]$ 内严格小于 $a_i$ 的元素个数，即

$\text{contrib}(i, j) = |\{k \in [i, j] \mid a_k < a_i\}|$。

请你计算并输出所有相邻等值对的贡献之和。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数
$T (1 \leq T \leq 10^4)$
代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数
  $n (1 \leq n \leq 2 \times 10^5)$
  表示数组长度；
• 第二行输入 $n$ 个整数
  $a_1, a_2, \dots, a_n (1 \leq a_i \leq n)$
  表示数组元素。

除此之外，保证单个测试文件的 $n$ 和不超过
$2 \times 10^5$。

输出描述

对于每一组测试数据，新起一行，输出一个整数表示答案。

样例1

输入

2
5
2 1 2 1 2
6
3 2 2 1 3 2

输出

2
4

说明

对应第一组测试数据）：

• 值 $2$ 的位置为 $1,3,5$，相邻等值对为 $(1,3)$ 与 $(3,5)$；区间 $[1,3] = \{2,1,2\}$ 中小于 $2$ 的有 $1$ 个元素 $1$；区间 $[3,5] = \{2,1,2\}$ 中小于 $2$ 的也有 $1$ 个元素 $1$；

• 值 $1$ 的位置为 $2,4$，相邻等值对为 $(2,4)$；区间 $[2,4] = \{1,2,1\}$ 中小于 $1$ 的元素为 $0$ 个；

• 合计得到 $1+1+0=2$。