[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 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ of length 𝑛$n$ of numbers 0,…,𝑛−1$0,\dots ,n-1$. Count the number of subsegments 1≤𝑙≤𝑟≤𝑛$1\le l\le r\le n$ of this permutation such that 𝑚𝑒𝑥(𝑝𝑙,𝑝𝑙+1,…,𝑝𝑟)>𝑚𝑒𝑑(𝑝𝑙,𝑝𝑙+1,…,𝑝𝑟)$mex(p_l,p_{l+1},\dots ,p_r)>med(p_l,p_{l+1},\dots ,p_r)$.

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

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

• 𝑚𝑒𝑑(0,1,2,3)=1$med(0,1,2,3)=1$
• 𝑚𝑒𝑑(0,4,1,3)=1$med(0,4,1,3)=1$
• 𝑚𝑒𝑑(5,4,0,1,2)=2$med(5,4,0,1,2)=2$

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

Input

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line of each test case contains exactly 𝑛$n$ integers: 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ (0≤𝑝𝑖≤𝑛−1$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⋅105$2\cdot {10}^5$.

Output

For each test case print the answer in a single line: the number of subsegments 1≤𝑙≤𝑟≤𝑛$1\le l\le r\le n$ of this permutation such that 𝑚𝑒𝑥(𝑝𝑙,𝑝𝑙+1,…,𝑝𝑟)>𝑚𝑒𝑑(𝑝𝑙,𝑝𝑙+1,…,𝑝𝑟)$mex(p_l,p_{l+1},\dots ,p_r)>med(p_l,p_{l+1},\dots ,p_r)$.

Note

The first test case contains exactly one subsegment and 𝑚𝑒𝑥(0)=1>𝑚𝑒𝑑(0)=0$mex(0)=1>med(0)=0$ on it.

In the third test case, on the following subsegments: [1,0]$[1,0]$, [0]$[0]$, [1,0,2]$[1,0,2]$ and [0,2]$[0,2]$, 𝑚𝑒𝑥$mex$ is greater than 𝑚𝑒𝑑$med$.

In the fourth test case, on the following subsegments: [0,2]$[0,2]$, [0]$[0]$, [0,2,1]$[0,2,1]$ and [0,2,1,3]$[0,2,1,3]$, 𝑚𝑒𝑥$mex$ greater than 𝑚𝑒𝑑$med$.