A15125 | Diverse Segments

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}, \ldots, 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$ .

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, \ldots, 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$ .

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