CF1684F Diverse Segments

给定长度为 $n$ 的序列 $a$，以及 $m$ 个数对 $(l_i,r_i)$。 你可以进行下列操作至多一次： - 选择序列 $a$ 的一个子段，并将其中的每个元素的值都改成任意整数。 你需要保证执行完操作之后，对于每个整数 $i(1\leq i\leq m)$，都有 $a[l_i,r_i]$ 中所有元素互不相同。 你需要最小化操作时选择的子段的长度，并求出这个长度的最小值。 特别的如果没有必要进行操作，答案为 $0$。

第一行输入一个整数 $t(1\leq t\leq100)$ 表示数据组数，接下来对于每组数据： 第一行输入两个整数 $n,m(1\leq n,m,\sum n,\sum m\leq2\times10^5)$ 表示序列长度和给定的数对数。 接下来一行输入 $n$ 个整数表示 $a_1,a_2,\cdots,a_n(1\leq a_i\leq10^9)$。 接下来输入 $m$ 行，其中第 $i$ 行输入两个整数表示 $l_i,r_i(1\leq l_i\leq r_i\leq n)$。

对于每组数据： 输出进行操作的子段的长度的最小值。 ### 样例解释 对于第一组数据，我们可以选择子段 $[1,2]$ 并将序列改成 $[114,514,2,1,3,3,5]$，此时： - 对于第一个数对 $(1,4)$，我们有 $a[1,4]=[114,514,2,1]$。 - 对于第二个数对 $(4,5)$，我们有 $a[4,5]=[1,3]$。 - 对于第三个数对 $(2,4)$，我们有 $a[2,4]=[514,2,1]$。 显然每个数对都满足要求，且我们可以证明没有更优的答案，因此答案为 $2$。 对于第二组数据，我们没有必要进行操作。 对于第三组数据，我们可以选择子段 $[1,1]$ 并将序列改成 $[1,7,5,6]$。

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.