题目描述

定义长为 $n$ 的序列 $a$ 的一个非空连续子段是合法的，当且仅当其中所有出现过的元素出现次数全相等。

求合法的非空子段个数。

两个子段不同当且仅当它们在原序列中的出现位置不同。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组数据格式如下：

第一行一个整数 $n$。

接下来一行 $n$ 个整数，描述序列 $a$。

输出格式

输出 $T$ 行，每行一个整数，表示答案。

样例 1 输入

5
9
1 1 1 2 2 2 3 3 3
4
1 1 2 2
5
1 1 2 2 1
10
1 2 2 1 1 2 3 2 3 3
12
1 1 2 3 3 2 1 2 3 3 2 1

样例 1 输出

25
8
11
26
34

数据范围与约定

测试数据满足：

$$T\ge 1,\qquad 1\le n,\qquad \sum n\le 10^6,\qquad 1\le a_i\le n.$$

子任务编号	$n$ / $\sum n$	特殊性质	分值
1	$n\le 100,\ \sum n\le 1000$	无	8
2	$n\le 8000,\ \sum n\le 4\times 10^4$
3	$\sum n\le 2\times 10^5$	$1\le a_i\le 4$	16
4		$a$ 序列每个元素在 $[1,n]$ 均匀随机	12
5		$1\le a_i\le 14$	20
6		无	12
7	$\sum n\le 5\times 10^5$
8	$\sum n\le 10^6$