题目背景

下图是一个经典算法的错误实现。

题目描述

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

求合法的非空子段个数。两个子段不同当且仅当它们在原序列中的出现位置不同。

输入格式

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

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

第一行一个整数 $n$。

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

输出格式

$T$ 行，每行一个整数，表示一组数据的答案。

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

25
8
11
26
34

提示

样例解释 #1

对于第三组数据，合法的连续非空子序列如下：

• $[1,1]$
• $[1,2]$
• $[1,4]$
• $[2,2]$
• $[2,3]$
• $[2,5]$
• $[3,3]$
• $[3,4]$
• $[4,4]$
• $[4,5]$
• $[5,5]$

数据范围

本题采取子任务依赖，未通过当前子任务依赖的子任务会导致当前子任务得零分。

对于 $100\%$ 的数据，$T\ge 1,1\le n,\sum n\le 10^6,1\le a_i\le n$。