F. MEX vs MEDtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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}) = 3med 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}) = 2A sequence of n numbers is called a permutation if it contains all the numbers from 0 to n - 1 exactly once.InputThe 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.OutputFor 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).ExampleInput
81021 031 0 240 2 1 353 1 0 2 462 0 4 1 3 583 7 2 6 0 1 5 442 0 1 3Output
1
2
4
4
8
8
15
6
NoteThe 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.
81021 031 0 240 2 1 353 1 0 2 462 0 4 1 3 583 7 2 6 0 1 5 442 0 1 3
1 2 4 4 8 8 15 6 
['math', 'two pointers', '*2000']