## GUPTA MECHANICAL

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

## [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).

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\le j\le m$ all elements ${a}_{{l}_{j}},{a}_{{l}_{j}+1},\dots ,{a}_{{r}_{j}-1},{a}_{{r}_{j}}$ should be distinct.

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

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($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\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 ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($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\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\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$.