C. Stay in Your Lane
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ positive integers.

For a pair of indices $$$(l, r)$$$ with $$$1 \le l \le r \le n$$$, consider the subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ — the contiguous block of elements from index $$$l$$$ to index $$$r$$$. This subarray is self-contained if every one of its elements lies in the range $$$[l, r]$$$; formally, if $$$l \le a_i \le r$$$ holds for every $$$i$$$ with $$$l \le i \le r$$$.

Count the number of self-contained subarrays of $$$a$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — 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$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the number of self-contained subarrays of $$$a$$$.

Example
Input
3
5
1 3 2 5 4
4
2 1 4 3
1
1
Output
6
3
1
Note

In the first test case, $$$a = [1, 3, 2, 5, 4]$$$. The self-contained subarrays are:

  • $$$(l, r) = (1, 1)$$$: the element $$$1$$$ lies in $$$[1, 1]$$$;
  • $$$(l, r) = (2, 3)$$$: the elements $$$3, 2$$$ lie in $$$[2, 3]$$$;
  • $$$(l, r) = (4, 5)$$$: the elements $$$5, 4$$$ lie in $$$[4, 5]$$$;
  • $$$(l, r) = (1, 3)$$$: the elements $$$1, 3, 2$$$ lie in $$$[1, 3]$$$;
  • $$$(l, r) = (2, 5)$$$: the elements $$$3, 2, 5, 4$$$ lie in $$$[2, 5]$$$;
  • $$$(l, r) = (1, 5)$$$: the elements $$$1, 3, 2, 5, 4$$$ lie in $$$[1, 5]$$$.
This gives $$$6$$$ self-contained subarrays. As an example of a pair that does not qualify, $$$(l, r) = (2, 4)$$$ fails because $$$a_4 = 5$$$ does not lie in $$$[2, 4]$$$.

In the second test case, $$$a = [2, 1, 4, 3]$$$, the self-contained subarrays are $$$(1, 2)$$$, $$$(3, 4)$$$, and $$$(1, 4)$$$, for a total of $$$3$$$.

In the third test case, $$$a = [1]$$$, and its only subarray $$$(1, 1)$$$ is self-contained since $$$a_1 = 1$$$, for a total of $$$1$$$.