Description:
You are given a permutation $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ of numbers $$$0, \ldots, n - 1$$$. Count the number of subsegments $$$1 \leq l \leq r \leq n$$$ of this permutation such that $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.
$$$mex$$$ of $$$S$$$ is the smallest non-negative integer that does not occur in $$$S$$$. For example:
- $$$mex({0, 1, 2, 3}) = 4$$$
- $$$mex({0, 4, 1, 3}) = 2$$$
- $$$mex({5, 4, 0, 1, 2}) = 3$$$
$$$med$$$ of the set $$$S$$$ is the median of the set, i.e. the element that, after sorting the elements in non-decreasing order, will be at position number $$$\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$$$ (array elements are numbered starting from $$$1$$$ and here $$$\left \lfloor{v} \right \rfloor$$$ denotes rounding $$$v$$$ down.). For example:
- $$$med({0, 1, 2, 3}) = 1$$$
- $$$med({0, 4, 1, 3}) = 1$$$
- $$$med({5, 4, 0, 1, 2}) = 2$$$
A sequence of $$$n$$$ numbers is called a permutation if it contains all the numbers from $$$0$$$ to $$$n - 1$$$ exactly once.
Input Format:
The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4$$$), the number of test cases.
The descriptions of the test cases follow.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the permutation $$$p$$$.
The second line of each test case contains exactly $$$n$$$ integers: $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \leq p_i \leq n - 1$$$), elements of permutation $$$p$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output Format:
For each test case print the answer in a single line: the number of subsegments $$$1 \leq l \leq r \leq n$$$ of this permutation such that $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.
Note:
The first test case contains exactly one subsegment and $$$mex({0}) = 1 > med({0}) = 0$$$ on it.
In the third test case, on the following subsegments: $$$[1, 0]$$$, $$$[0]$$$, $$$[1, 0, 2]$$$ and $$$[0, 2]$$$, $$$mex$$$ is greater than $$$med$$$.
In the fourth test case, on the following subsegments: $$$[0, 2]$$$, $$$[0]$$$, $$$[0, 2, 1]$$$ and $$$[0, 2, 1, 3]$$$, $$$mex$$$ greater than $$$med$$$.