Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×
D. Array Transformation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  • if $$$a = [7, 7, 7, 1, 7, 4, 1]$$$, then $$$b = [1, 2, 3, 1, 4, 1, 2]$$$;
  • if $$$a = [1, 2, 1, 2, 1, 2]$$$, then $$$b = [1, 1, 2, 2, 3, 3]$$$;
  • if $$$a = [1, 2, 3, 3, 2, 1]$$$, then $$$b = [1, 1, 1, 2, 2, 2]$$$.

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.

Input

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$$$.

Output

For each test case, output one integer — the number of subsegments of the array $$$x$$$ that are good sequences.

Example
Input
6
8
1 1 2 2 2 1 2 3
10
1 1 1 1 1 1 1 1 1 1
5
5 4 3 2 1
10
1 2 3 1 2 1 2 1 3 1
6
1 2 3 4 5 1
15
1 1 2 1 2 2 3 2 1 2 3 3 2 1 2
Output
9
55
1
24
7
18
Note

In the first test case, there are $$$9$$$ good subsegments:

  • $$$x_1 = [1]$$$;
  • $$$x_1, x_2 = [1, 1]$$$;
  • $$$x_1, \dots, x_3 = [1, 1, 2]$$$;
  • $$$x_1, \dots, x_4 = [1, 1, 2, 2]$$$;
  • $$$x_2 = [1]$$$;
  • $$$x_2, x_3 = [1, 2]$$$;
  • $$$x_6 = [1]$$$;
  • $$$x_6, x_7 = [1, 2]$$$;
  • $$$x_6, \dots, x_8= [1, 2, 3]$$$.

In the second test case, any subsegment is good.

In the third test case, there is only one good subsegment — $$$x_5 = [1]$$$.