GUPTA MECHANICAL

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

Sunday, 16 October 2022

[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 p1,p2,,pn of length n of numbers 0,,n1. Count the number of subsegments 1lrn of this permutation such that mex(pl,pl+1,,pr)>med(pl,pl+1,,pr).

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 |S|+12 (array elements are numbered starting from 1 and here v 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 n1 exactly once.

Input

The first line of the input contains a single integer t (1t104), the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single integer n (1n2105), the length of the permutation p.

Solution Click Below:-  ðŸ‘‰CLICK HERE👈
👇👇👇👇👇

The second line of each test case contains exactly n integers: p1,p2,,pn (0pin1), elements of permutation p.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case print the answer in a single line: the number of subsegments 1lrn of this permutation such that mex(pl,pl+1,,pr)>med(pl,pl+1,,pr).


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.

No comments:

Post a Comment