P12608 D. Goners' Gold-Grinding Garage

The problem background is not important.

You are given an integer sequence of size $n$. A **non-empty contiguous** subsequence of $a$ is called beautiful if and only if every element appearing in it occurs the same number of times. Your task is to compute the number of beautiful contiguous subsequences. The same beautiful subsequence appearing at different positions is counted multiple times.

The first line contains a single integer $t$ — the number of test cases. For each test case, the first line contains an integer $n$. The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

For each test case, print a single integer — the number of beautiful contiguous subsequences in that test case.

### Sample Explanation In the third example, the intervals representing all beautiful subsequences are: - $[1,1]$ - $[1,2]$ - $[1,4]$ - $[2,2]$ - $[2,3]$ - $[2,5]$ - $[3,3]$ - $[3,4]$ - $[4,4]$ - $[4,5]$ - $[5,5]$ ### Data Range The problem uses subtask dependencies: failing a prerequisite subtask will result in a score of zero for any subtask. It is guaranteed that for all testcases, $T\ge 1,1\le n,\sum n\le 10^6,1\le a_i\le n$。 |#|$n\le$|$\sum n\le\ $|Special Constraints|Points|Time Limit|Depends On| |:-------:|:-:|:-:|:-----:|:--:|:--:|:-:| |$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$|all $a_i$s are generated uniformly random from $[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$|