CF1744F.MEX vs MED

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) \gt 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.

给你一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，其中包含数字 $0, \ldots, n - 1$ 各恰好一次。请统计满足以下条件的子段（连续子数组）$1 \leq l \leq r \leq n$ 的个数：

$$mex(p_l, p_{l+1}, \ldots, p_r) \gt med(p_l, p_{l+1}, \ldots, p_r).$$

集合 $S$ 的 $mex$ 指不在 $S$ 中出现的最小非负整数。例如：

• $mex({0, 1, 2, 3}) = 4$
• $mex({0, 4, 1, 3}) = 2$
• $mex({5, 4, 0, 1, 2}) = 3$

集合 $S$ 的 $med$ 指其中位数，即：将 $S$ 中所有元素按非降序排序后，位于第 $\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$ 个位置上的元素（数组下标从 $1$ 开始计数；此处 $\left \lfloor{v} \right \rfloor$ 表示对 $v$ 向下取整）。例如：

• $med({0, 1, 2, 3}) = 1$
• $med({0, 4, 1, 3}) = 1$
• $med({5, 4, 0, 1, 2}) = 2$

若一个由 $n$ 个数组成的序列恰好包含 $0$ 到 $n - 1$ 中的每个数各一次，则称其为一个排列。

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

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示排列 $p$ 的长度。

每个测试用例的第二行包含恰好 $n$ 个整数：$p_1, p_2, \ldots, p_n$（$0 \leq p_i \leq n - 1$），即排列 $p$ 的元素。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

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) \gt med(p_l, p_{l+1}, \ldots, p_r)$.

对于每个测试用例，在一行中输出答案：满足 $\mathrm{mex}(p_l, p_{l+1}, \ldots, p_r) \gt \mathrm{med}(p_l, p_{l+1}, \ldots, p_r)$ 的子段 $1 \leq l \leq r \leq n$ 的个数。

The first test case contains exactly one subsegment and $mex({0}) = 1 \gt 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$.

第一个测试用例恰好包含一个子段，且在其上满足 $mex({0}) = 1 \gt med({0}) = 0$。

在第三个测试用例中，在以下子段上：$[1, 0]$、$[0]$、$[1, 0, 2]$ 和 $[0, 2]$，有 $mex > med$。

在第四个测试用例中，在以下子段上：$[0, 2]$、$[0]$、$[0, 2, 1]$ 和 $[0, 2, 1, 3]$，有 $mex > med$。