P12608 骷髅打金服

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

长为 $n$ 的序列 $a$ 的一个非空连续子段是合法的，当且仅当其中**所有出现过的元素**出现次数全相等。 求合法的非空子段个数。两个子段不同当且仅当它们在原序列中的出现位置不同。

第一行一个整数 $T$，表示数据组数。 接下来 $T$ 组数据，每组数据格式如下： 第一行一个整数 $n$。 接下来一行 $n$ 个整数，描述序列 $a$。

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

### 样例解释 #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$。 |子任务|$n\le$|$\sum n\le$|特殊性质|分值|时限|依赖子任务| |:-------:|:-:|:-:|:-----:|:--:|:--:|:-:| |$1$|$100$|$1000$|-|$10$|1s| | |$2$|$8000$|$4\times 10^4$|-|$10$|1s|$1$| |$3$|-|$2\times 10^5$|$1\le a_i \le 4$|$20$|1s| | |$4$|-|$2\times 10^5$|$a$ 的每个元素在 $[1,n]$ 均匀随机|$10$|1s| | |$5$|-|$2\times 10^5$|$1\le a_i\le 14$|$20$|1s|$3$| |$6$|-|$2\times 10^5$|-|$10$|1s|$1\sim 5$| |$7$|-|$5\times 10^5$|-|$10$|2s|$1\sim 6$| |$8$|-|$10^6$|-|$10$|3s|$1\sim 7$|