#P18320. Score Sum

Score Sum

Score Sum

设数组 AA 的长度为 NN。下面定义它的得分函数。

令 d(L,R)d(L,R) 表示子数组 [AL,AL+1,…,AR][A_L,A_{L+1},\ldots,A_R] 中不同元素的数量,并定义

f(L,R)=(R−L+1)−d(L,R).f(L,R)=(R-L+1)-d(L,R).

在所有满足 1≤L≤R≤N1\le L\le R\le N 的数对中,先选择使 f(L,R)f(L,R) 最大的数对。如果有多个,选择其中 R−L+1R-L+1 最小的数对。如果仍有多个,可以任选一个。

最终定义 score⁡(A)=R−L+1\operatorname{score}(A)=R-L+1,也就是先最大化 ff、再最小化长度后所得到的子数组长度。

单独求一个数组的得分太简单了,因此现在需要对所有子数组求和。给定数组 AA,求

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

其中 A[L,R]A[L,R] 表示子数组 [AL,AL+1,…,AR][A_L,A_{L+1},\ldots,A_R]。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例包含两行:

  • 第一行包含整数 NN,表示数组长度。
  • 第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

对于每个测试用例,输出一行,包含所有子数组得分之和。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • 1≤N≤2⋅1051\le N\le2\cdot10^5;
  • 1≤Ai≤N1\le A_i\le N;
  • 全部测试用例的 NN 之和不超过 2⋅1052\cdot10^5。

样例

输入

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

输出

4
8
26
62

说明

第一个测试用例共有三个子数组:两个不同位置上的 [1][1],以及一个 [1,1][1,1]。

  • 对于 [1][1],只有一个可选区间,所以得分为1。
  • 对于 [1,1][1,1],只有整个长度2的区间能够取得最大的 ff 值,所以得分为2。

因此答案是 1+1+2=41+1+2=4。