C. Problem from Ust-Katav
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation$$$^{\text{∗}}$$$ of integers $$$p_1, p_2, \ldots, p_n$$$.

We will call a subarray of the permutation $$$p_l, p_{l + 1}, \ldots, p_r$$$ good if there does not exist another subarray of the same length with the same value of the minimum element in the permutation $$$p$$$.

Find the number of good subarrays of the permutation $$$p$$$.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$).

The second line of each test case contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_{i} \leq n$$$).

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

Output

For each test case, output the number of good subarrays in one line.

Example
Input
4
1
1
2
1 2
4
3 2 4 1
7
3 7 5 1 6 4 2
Output
1
3
8
14
Note

In the first test case, the only subarray is good.

In the second test case, all subarrays are good.

In the third test case, the subarrays $$$[p_1, p_2]$$$ and $$$[p_2, p_3]$$$ are not good, because they have the same length and the same value of the minimum element. All other subarrays are good.