A. Complete Subarrays
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ of length $$$n$$$, where each element is an integer between $$$1$$$ and $$$10^9$$$.

For a value $$$x$$$, let $$$\text{freq}(x)$$$ denote the number of times $$$x$$$ appears in the entire array $$$a$$$.

A contiguous subarray $$$a[l \ldots r]$$$ is called complete if the following condition holds:

  • For every value $$$x$$$ that appears in $$$a[l \ldots r]$$$, the number of times $$$x$$$ appears in $$$a[l \ldots r]$$$ is exactly $$$\text{freq}(x)$$$.

In other words, if a value appears in the subarray, then all of its occurrences in the whole array must be contained within that subarray.

You are given multiple test cases. For each test case, determine the total number of complete subarrays of $$$a$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$($$$1 \le n \le 2 \times 10^5$$$) — the length of the array.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, print a single integer — the number of complete subarrays of $$$a$$$.

Example
Input
5
5
3 2 3 1 1
2
2 2
9
7 2 5 2 9 9 3 3 5
10
5 10 6 1 9 2 7 2 4 3
9
7 1 6 5 1 2 9 6 3
Output
4
1
6
37
10
Note

In the first test case, subarrays $$$[2]$$$,$$$[1,1]$$$,$$$[3,2,3]$$$ and $$$[3,2,3,1,1]$$$ are complete while $$$[2,3]$$$ is not as it does not contain all occurrences of $$$3$$$.Thus,there are $$$4$$$ complete subarrays.

In the second test case, there is only one complete subarray, $$$[2,2]$$$.