Diverse Segments
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 2600
Tags: data structures, two pointers

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

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case you can perform the operation on the segment $$$[1, 2]$$$ and make $$$a = [5, 6, 2, 1, 3, 3, 5]$$$. Then the elements on each segment are distinct.

- On the segment $$$[1, 4]$$$ there are $$$[5, 6, 2, 1]$$$.
- On the segment $$$[4, 5]$$$ there are $$$[1, 3]$$$.
- On the segment $$$[2, 4]$$$ there are $$$[6, 2, 1, 3]$$$.

This way on each of the given segments all elements are distinct. Also, it is impossible to change any single integer to make elements distinct on each segment. That is why the answer is $$$2$$$.

In the second test case the elements on each segment are already distinct, so we should not perform the operation.

In the third test case we can replace the first $$$5$$$ by $$$1$$$. This way we will get $$$[1, 7, 5, 6]$$$ where all elements are distinct so on each given segment all elements are distinct.

Example input:
5
7 3
1 1 2 1 3 3 5
1 4
4 5
2 4
5 2
10 1 6 14 1
4 5
2 4
4 5
5 7 5 6
2 2
1 3
2 4
3 3
3 4
7 3
2 2 2 7 8 2 2
4 4
4 4
5 5
1 1
123
1 1

Example output:
2
0
1
0
0

Editorial:
Let's say the answer is $$$[L, R]$$$. Let's consider all given segments. There should be no two equal elements that are in the same given segment and are not in $$$[L, R]$$$, i.e. at least one of them should be in the answer. Let's find such segment of minimal length for $$$L = 1$$$. To do that let's for each $$$r$$$ find such minimal $$$l$$$ that on segment $$$[l, r]$$$ all elements are distinct. Let's say that $$$l = f(r)$$$. This could be done using two pointers, maintaining current set of elements and checking whether the considered element is not in the set. Let's say we are given a segment $$$[l_j, r_j]$$$. If $$$f(r_j) \le l_j$$$ then this segment is already fine. Else for $$$L = 1$$$ this condition holds $$$R \ge f(r_j) - 1$$$. Minimal $$$R$$$ that meets all the inequalitites will be the answer.
Now let's find out how to find $$$R$$$ while increasing $$$L$$$ by $$$1$$$. If we increase $$$L$$$ then $$$R$$$ can not decrease. Also if $$$[L + 1, R]$$$ can not be the answer then in some of given segments there are two equal elements $$$a_L$$$ and $$$a_j$$$. If $$$j < L$$$ then the left endpoint can not be greater than $$$L$$$. Else $$$j > R$$$. Then we have to make $$$R = j$$$ and this $$$j$$$ should be minimal. This $$$j$$$ could be found, for example, by binary search in $$$cnt$$$ array. To check whether two elements are in the same segments it is possible to use a segment tree or a Fenwick tree. It is possible to store for each $$$i$$$ such maximal $$$r_j$$$ that there is a given segment $$$[l_j, r_j]$$$ and $$$l_j \le i$$$.
The final answer will be the minimal length of $$$[L, R]$$$ for all $$$L$$$.