CF1527C.Sequence Pair Weight

The weight of a sequence is defined as the number of unordered pairs of indexes $(i,j)$ (here $i \lt j$) with same value ($a_{i} = a_{j}$). For example, the weight of sequence $a = [1, 1, 2, 2, 1]$ is $4$. The set of unordered pairs of indexes with same value are $(1, 2)$, $(1, 5)$, $(2, 5)$, and $(3, 4)$.

You are given a sequence $a$ of $n$ integers. Print the sum of the weight of all subsegments of $a$.

A sequence $b$ is a subsegment of a sequence $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

序列的权重定义为满足 $a_i = a_j$ 的无序索引对 $(i, j)$（其中 $i < j$）的个数。例如，序列 $a = [1, 1, 2, 2, 1]$ 的权重为 $4$。这些满足条件的无序索引对为 $(1, 2)$、$(1, 5)$、$(2, 5)$ 和 $(3, 4)$。

给定一个包含 $n$ 个整数的序列 $a$，请输出 $a$ 的所有子段（subsegment）的权重之和。

若序列 $b$ 可通过从序列 $a$ 的开头删除若干（可能为零个或全部）元素，并从结尾删除若干（可能为零个或全部）元素而得到，则称 $b$ 是 $a$ 的一个子段。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). 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 second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。

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

For each test case, print a single integer — the sum of the weight of all subsegments of $a$.

对于每个测试用例，输出一个整数——数组 $a$ 的所有子段的权重之和。

• In test case $1$, all possible subsegments of sequence $[1, 2, 1, 1]$ having size more than $1$ are:

  1. $[1, 2]$ having $0$ valid unordered pairs;
  2. $[2, 1]$ having $0$ valid unordered pairs;
  3. $[1, 1]$ having $1$ valid unordered pair;
  4. $[1, 2, 1]$ having $1$ valid unordered pairs;
  5. $[2, 1, 1]$ having $1$ valid unordered pair;
  6. $[1, 2, 1, 1]$ having $3$ valid unordered pairs.Answer is $6$.

• In test case $2$, all elements of the sequence are distinct. So, there is no valid unordered pair with the same value for any subarray. Answer is $0$.

• 在测试用例 $1$ 中，序列 $[1, 2, 1, 1]$ 的所有长度大于 $1$ 的可能子段为：

  1. $[1, 2]$，包含 $0$ 个有效的无序对；
  2. $[2, 1]$，包含 $0$ 个有效的无序对；
  3. $[1, 1]$，包含 $1$ 个有效的无序对；
  4. $[1, 2, 1]$，包含 $1$ 个有效的无序对；
  5. $[2, 1, 1]$，包含 $1$ 个有效的无序对；
  6. $[1, 2, 1, 1]$，包含 $3$ 个有效的无序对。答案为 $6$。

• 在测试用例 $2$ 中，序列的所有元素互不相同。因此，任意子数组中均不存在值相同的有效无序对。答案为 $0$。