J. Odd Minimum Subarrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.

A non-empty subarray is a contiguous segment $$$a_l,a_{l+1},\ldots,a_r$$$ for some $$$1 \le l \le r \le n$$$. It is called good if its minimum element occurs an odd number of times within it.

Find the number of good subarrays of $$$a$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

Each test case consists of two lines.

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 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 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, print one integer — the number of good subarrays.

Example
Input
4
4
1 3 1 2
2
1 1
5
3 4 2 5 2
10
9 2 5 3 5 7 5 4 3 2
Output
8
2
12
50