假设我们有一个包含 $N$ 个元素的数组 $A$。我们按如下方式定义数组 $A$ 的得分函数。

令 $d(L, R)$ 表示子数组 $[A_L, A_{L+1}, \dots, A_R]$ 中不同元素的个数。 定义 $f(L, R) = (R - L + 1) - d(L, R)$，即从 $L$ 到 $R$ 的子数组长度减去其中不同元素的个数。

考虑满足 $1 \le L \le R \le N$ 且使 $f(L, R)$ 取得最大值的数对 $(L, R)$。如果存在多个这样的数对，则选择 $(R - L + 1)$ 值最小的那一个。如果仍然存在多个这样的数对，则任选一个。

最后，我们定义 $score(A)$ 为 $(R - L + 1)$。也就是说，它是所有具有最大 $f$ 值且在这些最大值中长度最小的子数组的长度。

由于求得分太简单了，我们增加了一个更难的任务：对所有子数组求和。 形式化地，给定一个包含 $N$ 个元素的数组 $A$，求下式的值：

$$\sum_{L=1}^{N} \sum_{R=L}^{N} score(A[L, R])$$

其中 $A[L, R]$ 表示子数组 $[A_L, A_{L+1}, \dots, A_R]$。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含两行输入：
  • 第一行包含 $N$，即数组 $A$ 的大小。
  • 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

对于每个测试用例，输出一行，表示数组 $A$ 所有子数组的得分之和。

数据范围

• $1 \le T \le 10^4$
• $1 \le N \le 2 \cdot 10^5$
• $1 \le A_i \le N$
• 所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。

样例

样例输入 1

4
2
1 1
3
1 3 1
5
1 3 1 2 3
7
1 2 3 1 5 3 1

样例输出 1

4
8
26
62

说明 1

测试用例 1：总共有 3 个子数组——2 个重复出现的 $[1]$ 和 1 个 $[1, 1]$。

• $[1]$：$score([1])$ 显然就是 1，因为只有一对 $L=1, R=1$ 可选。
• $[1, 1]$：$L=1, R=2$ 是 $f$ 值最大的唯一区间。因此，$score([1, 1]) = 2$。

总和为 $1 + 1 + 2 = 4$。