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

给你一个包含 $n$ 个整数的数组 $a$，以及该数组的 $m$ 个子区间。第 $j$ 个区间的左右端点分别为 $l_j$ 和 $r_j$。

你最多可以执行一次操作：在该操作中，任选数组 $a$ 的一个子区间，并将该子区间内的每个元素替换为任意整数（你也可以选择保持某些元素不变）。

你需要执行该操作，使得给定的 $m$ 个区间各自内部的元素互不相同。更准确地说，对每个 $1 \le j \le m$，子数组 $a_{l_{j}}, a_{l_{j}+1}, \ldots, a_{r_{j}-1}, a_{r_{j}}$ 中的所有元素必须互异。

你希望避免在过长的区间上执行该操作，因此你需要找出满足上述条件所需的最短操作区间长度。若无需执行该操作，则答案为 $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$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示数组的大小和区间的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

接下来的 $m$ 行中，每行包含两个整数 $l_j$、$r_j$（$1 \le l_j \le r_j \le n$），表示第 $j$ 个区间的左右端点。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $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$.

对于每个测试用例，输出一个整数——即能够通过执行一次操作使得所有给定区间内的元素互不相同的最短区间的长度。如果无需执行该操作，则输出 $0$。

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.

在第一个测试用例中，你可以对区间 $[1, 2]$ 执行操作，使数组变为 $a = [5, 6, 2, 1, 3, 3, 5]$。此时，每个给定区间内的元素均互不相同。

• 在区间 $[1, 4]$ 上，元素为 $[5, 6, 2, 1]$。
• 在区间 $[4, 5]$ 上，元素为 $[1, 3]$。
• 在区间 $[2, 4]$ 上，元素为 $[6, 2, 1, 3]$。

这样，所有给定区间内的元素均互不相同。此外，仅修改单个整数无法使所有给定区间内的元素均互不相同。因此答案为 $2$。

在第二个测试用例中，每个给定区间内的元素已经互不相同，因此无需执行任何操作。

在第三个测试用例中，我们可以将第一个 $5$ 替换为 $1$。这样得到数组 $[1, 7, 5, 6]$，其中所有元素互不相同，故每个给定区间内的元素也均互不相同。