## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] MEX vs MED Codeforces Solution | Solution Codeforces

F. MEX vs MED
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation ${p}_{1},{p}_{2},\dots ,{p}_{n}$ of length $n$ of numbers $0,\dots ,n-1$. Count the number of subsegments $1\le l\le r\le n$ of this permutation such that $mex\left({p}_{l},{p}_{l+1},\dots ,{p}_{r}\right)>med\left({p}_{l},{p}_{l+1},\dots ,{p}_{r}\right)$.

$mex$ of $S$ is the smallest non-negative integer that does not occur in $S$. For example:

• $mex\left(0,1,2,3\right)=4$
• $mex\left(0,4,1,3\right)=2$
• $mex\left(5,4,0,1,2\right)=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 $⌊\frac{|S|+1}{2}⌋$ (array elements are numbered starting from $1$ and here $⌊v⌋$ denotes rounding $v$ down.). For example:

• $med\left(0,1,2,3\right)=1$
• $med\left(0,4,1,3\right)=1$
• $med\left(5,4,0,1,2\right)=2$

A sequence of $n$ numbers is called a permutation if it contains all the numbers from $0$ to $n-1$ exactly once.

Input

The first line of the input contains a single integer $t$ $\left(1\le t\le {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\le n\le 2\cdot {10}^{5}$), the length of the permutation $p$.

Solution Click Below:-  👉
👇👇👇👇👇

The second line of each test case contains exactly $n$ integers: ${p}_{1},{p}_{2},\dots ,{p}_{n}$ ($0\le {p}_{i}\le 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

For each test case print the answer in a single line: the number of subsegments $1\le l\le r\le n$ of this permutation such that $mex\left({p}_{l},{p}_{l+1},\dots ,{p}_{r}\right)>med\left({p}_{l},{p}_{l+1},\dots ,{p}_{r}\right)$.

Note

The first test case contains exactly one subsegment and $mex\left(0\right)=1>med\left(0\right)=0$ on it.

In the third test case, on the following subsegments: $\left[1,0\right]$$\left[0\right]$$\left[1,0,2\right]$ and $\left[0,2\right]$$mex$ is greater than $med$.

In the fourth test case, on the following subsegments: $\left[0,2\right]$$\left[0\right]$$\left[0,2,1\right]$ and $\left[0,2,1,3\right]$$mex$ greater than $med$.