[Solution] Diverse Segments Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Diverse Segments Codeforces Solution | Codeforces Problem Solution 2022

F. Diverse Segments

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array 𝑎$a$ of 𝑛$n$ integers. Also you are given 𝑚$m$ subsegments of that array. The left and the right endpoints of the 𝑗$j$-th segment are 𝑙𝑗$l_j$ and 𝑟𝑗$r_j$ respectively.

You are allowed to make no more than one operation. In that operation you choose any subsegment of the array 𝑎$a$ and replace each value on this segment with any integer (you are also allowed to keep elements the same).

Solution Click Below:-  CLICK HERE

You have to apply this operation so that for the given 𝑚$m$ segments, the elements on each segment are distinct. More formally, for each 1≤𝑗≤𝑚$1\le j\le m$ all elements 𝑎𝑙𝑗,𝑎𝑙𝑗+1,…,𝑎𝑟𝑗−1,𝑎𝑟𝑗$a_{l_j},a_{l_j+1},\dots ,a_{r_j-1},a_{r_j}$ should be distinct.

Digit Minimization Codeforces Solution

Z mod X = C Codeforces Solution

Column Swapping Codeforces Solution

Traps Codeforces Solution

MEX vs DIFF Codeforces Solution

Diverse Segments Codeforces Solution

Euclid Guess Codeforces Solution

Hard Cut Codeforces Solution

You don't want to use the operation on a big segment, so you have to find the smallest length of a segment, so that you can apply the operation to this segment and meet the above-mentioned conditions. If it is not needed to use this operation, the answer is 0$0$.

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛,𝑚≤2⋅105$1\le n,m\le 2\cdot {10}^5$) — the size of the array and the number of segments respectively.

The next line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$) — the elements of 𝑎$a$.

Each of the next 𝑚$m$ lines contains two integers 𝑙𝑗$l_j$, 𝑟𝑗$r_j$ (1≤𝑙𝑗≤𝑟𝑗≤𝑛$1\le l_j\le r_j\le n$) — the left and the right endpoints of the 𝑗$j$-th segment.

It's guaranteed that the sum of 𝑛$n$ and the sum of 𝑚$m$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case output a single integer — the smallest length of a segment you can apply an operation on making the elements on all given segments distinct. If it is not needed to use the operation, output 0$0$.