MEX vs MED
Contest: Codeforces Round  828 (Div. 3)
Difficulty rating: 2000
Tags: math, two pointers

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)$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
8
1
0
2
1 0
3
1 0 2
4
0 2 1 3
5
3 1 0 2 4
6
2 0 4 1 3 5
8
3 7 2 6 0 1 5 4
4
2 0 1 3

Example output:
1
2
4
4
8
8
15
6

Editorial:
Let's learn how to count the number of subsegments where $$$\mathit{mex} > \mathit{mid}$$$ for a fixed value of $$$\mathit{mex}$$$.
Let's understand on which subsegments $$$\mathit{mex}$$$ has such a value. We understand that the numbers $$$0, 1, \ldots, \mathit{mex} - 1$$$ should be in this subsegment, the number $$$\mathit{mex}$$$ — should not, and then — does not matter . Let $$$\ell$$$ — be the index of the left-most occurrence of the numbers $$$0, 1, \ldots, \mathit{mex} - 1$$$, and $$$r$$$ — the right-most occurrence. Also, let $$$\mathit{pos}$$$ "be the index of the number $$$\mathit{mex}$$$. If $$$\ell < \mathit{pos} < r$$$, then there is no subsegment with the given $$$\mathit{ mex}$$$, otherwise let's think about how many numbers can be in a subsegment.
It is stated that if the length of a segment is $$$\leq 2 \cdot \mathit{mex}$$$, then $$$\mathit{mex} > \mathit{mid}$$$ on it, otherwise it is not true. Indeed, if the length of a segment is $$$\leq 2 \cdot \mathit{mex}$$$, then simply by the definition of the median, it will be among the first $$$\mathit{mex}$$$ numbers. On the other hand, if the length of the segment becomes longer, then according to the same definition of the median, it will no longer be among the first $$$\mathit{mex}$$$ numbers, which are equal to $$$0, 1, \ldots, \mathit{mex} - 1$$$.
It turns out that we need to count the number of subsegments of length $$$\leq 2 \cdot \mathit{mex}$$$ that contain the subsegment $$$\ell \ldots r$$$ inside themselves, but not $$$\mathit{pos}$$$. This, of course, can be done with large formulas and the like, but one more useful fact can be noticed!
If we iterate over $$$\mathit{mex}$$$ in ascending order, and at the same time maintain $$$\ell$$$ and $$$r$$$, then let's see what happens with a fixed $$$\mathit{mex}$$$ and a position of $$$\mathit{pos} $$$ (for convenience, let's assume that $$$\mathit{pos} < \ell$$$, since the second case is similar). In fact, you can simply iterate over the left border of our segment from $$$\mathit{pos} + 1$$$ to $$$\ell$$$, and then use a simpler formula to calculate the number of good subsegments with such fixed values.
Why can this left boundary be iterated for each $$$\mathit{mex}$$$ if $$$\mathit{pos} < \ell$$$ (correspondingly, if it were $$$\mathit{pos} > r$$$, then we would iterate over the right boundary) ? Let's remember that after this step, $$$\ell$$$ becomes equal to $$$\mathit{pos}$$$. That is, if we iterate over an element, then we move the corresponding border. And we can only move it $$$O(n)$$$ times.