假设你有一个数组$$$b$$$。最初,您还有一个集合 $$$S$$$,其中包含 $$$b$$$ 的所有不同元素。如果可以通过重复执行以下操作将数组 $$$b$$$ 清空,则该数组称为“orangutan-approved”:
- 在一个操作中,选择索引 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq |b|$$$) 使得 $$$v = b_l = b_{l+1} = \ldots = b_r$$$ 和 $$$v$$$ 出现在 $$$S$$$ 中。从$$$S$$$中删除$$$v$$$,并同时删除所有$$$b_i$$$,使得$$$l \leq i \leq r$$$。然后,相应地将元素 $$$b_{r+1}, b_{r+2}, \ldots$$$ 重新索引为 $$$b_l, b_{l+1}, \ldots$$$。
给您一个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$q$$$ 查询。
每个查询由两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 组成,您需要确定子数组 $$$a_{l}, a_{l+1}, \ldots, a_r$$$ 是否是猩猩认可的。
输入
第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 10^5$$$) - 分别是 $$$a$$$ 的大小和查询数量。
以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 数组 $$$a$$$ 的元素。
以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ — 每个查询的子数组的端点 ($$$1 \leq l \leq r \leq n$$$)。
保证所有测试用例的 $$$n$$$ 和 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,如果从 $$$l$$$ 到 $$$r$$$ 的子数组经过猩猩批准,则输出“YES”(不带引号),否则输出“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yES”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
3 4 2 1 2 2 1 1 4 1 3 5 3 1 2 1 2 1 2 5 3 5 1 3 8 4 1 2 3 2 1 3 2 3 1 5 2 8 3 5 6 8
输出 #1
YES YES NO YES YES YES NO YES YES
注意
在第一个测试用例的第一个查询中,答案是“是”。
- 最初,$$$S=\{1,2\}$$$ 和 $$$b=[1,2,2,1]$$$
- 选择$$$l=2$$$ 和$$$r=3$$$。由于$$$b_2=b_3=2$$$在$$$S$$$中,我们可以从数组中删除$$$b_2$$$和$$$b_3$$$,并从$$$S$$$中删除$$$2$$$。集合 $$$S$$$ 变为 $$$\{1\}$$$,数组变为 $$$[1,1]$$$。
- 选择$$$l=1$$$ 和$$$r=2$$$。由于$$$b_1=b_2=1$$$在$$$S$$$中,我们可以从数组中删除$$$b_1$$$和$$$b_2$$$,并从$$$S$$$中删除$$$1$$$。集合 $$$S$$$ 变为 $$$\{\}$$$,数组变为 $$$[]$$$。
- 由于数组现在为空,我们可以说原始数组是猩猩批准的。
在第二个测试用例的第一个查询中,答案是否定的,因为可以证明子数组 $$$[2,1,2,1]$$$ 不能通过任何有效操作序列变空。