Let the function $$$f$$$ take an array $$$a_1, a_2, \dots, a_n$$$ as input and return an array $$$b_1, b_2, \dots, b_n$$$ according to the following rule: the element $$$b_i$$$ is equal to the number of elements in the prefix of length $$$i$$$ of the array $$$a$$$ that are equal to $$$a_i$$$.
For example:
A sequence of numbers $$$x_1, x_2, \dots, x_n$$$ is called good if there is such an array $$$a$$$ that $$$f(a) = x$$$. For example, the sequence $$$x = [1, 2, 3, 1]$$$ is good, while $$$x = [1, 2, 2]$$$ and $$$x = [1, 2, 4]$$$ are not.
For a given array $$$x_1, x_2, \dots, x_n$$$, determine the number of its subsegments (subarrays of consecutive elements) that are good sequences.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array $$$x$$$.
The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le n$$$) — the array $$$x$$$ itself.
Additional constraint on the input data: the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.
For each test case, output one integer — the number of subsegments of the array $$$x$$$ that are good sequences.
681 1 2 2 2 1 2 3101 1 1 1 1 1 1 1 1 155 4 3 2 1101 2 3 1 2 1 2 1 3 161 2 3 4 5 1151 1 2 1 2 2 3 2 1 2 3 3 2 1 2
955124718
In the first test case, there are $$$9$$$ good subsegments:
In the second test case, any subsegment is good.
In the third test case, there is only one good subsegment — $$$x_5 = [1]$$$.