Count how many subsegment $[L, R]$ satisfying $R - L + 1 \geq 1$ and there is a kind of integer whose number of occurrences is strictly greater than the sum of others in $a[L..R]$.
输入解释
The first line contains an integer $T(T \le 15)$. Then $T$ test cases follow.
For each test case, input two lines.
For the first line, there is only one integer $n$ $(1 \leq n \leq 10^6)$.
The second line contains $n$ integers describing the array $a[1..n]$, while the restriction $0 \leq a_i \leq 10^6$ is guaranteed.
$\sum n<=6*10^6$
输出解释
For each test case, output a integer per line, denoting the answer of the problem.