← 返回题目列表

Codeforces · 1684/F

F. 不同的细分市场

中文机器翻译题面 查看原题

给定一个由 $$$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$$$。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例输出一个整数 - 段的最小长度,您可以应用使所有给定段上的元素不同的操作。如果不需要使用该运算,则输出$$$0$$$。

示例

输入 #1

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

输出 #1

2
0
1
0
0

注意

在第一个测试用例中,您可以对段 $$$[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$$$。

在第二个测试用例中,每个段上的元素已经不同,因此我们不应该执行该操作。

在第三个测试用例中,我们可以用 $$$1$$$ 替换第一个 $$$5$$$。这样我们将得到 $$$[1, 7, 5, 6]$$$,其中所有元素都是不同的,因此在每个给定的段上所有元素都是不同的。