CFCF2163D1.Diadrash (Easy Version)

这是该问题的简单版本。本版本与其他版本的区别在于，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次查询。只有当你解决了所有版本后，才可以进行 Hack。

本题为交互式题目。

有一个长度为 $n$ 的排列 $p$（从 $0$ 到 $n-1$ 的一个排列）对你隐藏。同时，给定 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$，其中 $1 \le l_i \le r_i \le n$。

你需要找出在输入给定的 $q$ 个区间中，$p$ 对应的子序列的最大 $\operatorname{MEX}$。形式化地，你需要找出 $ \max_{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])} $ 的值。为此，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次如下类型的询问：

• 任选任意两个整数 $1 \le l \le r \le n$，你会得到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。

$^*$ 长度为 $n$ 的排列是 $[0, 1, \ldots, n-1]$ 的一个重新排列，使得每个数仅出现一次。例如，序列 $[0, 3, 1, 2]$ 是一个排列，而 $[0, 0, 2, 1]$ 不是。

$^\dagger$ $\operatorname{MEX}$ 指的是序列中未出现的最小非负整数。例如，$\operatorname{MEX}([0, 0, 1, 3]) = 2$，$\operatorname{MEX}([1, 2, 2]) = 0$。

每组测试数据包含多组用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例组数。

每组测试数据的第一行包含两个整数 $n$ 和 $q$（$4 \le n \le 10^4$，$1 \le q \le 3 \times 10^5$），分别表示排列的长度和区间的数量。

接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。

保证所有测试用例中 $n$ 之和不超过 $10^4$，$q$ 之和不超过 $3 \times 10^5$。

额外约束：同一组测试数据内没有重复的区间。

在第一个样例中，隐藏的排列是 $p=[0,3,1,2]$，区间为 $[1,2]$，$[2,4]$，$[1,3]$。第三个区间是最优的，因为 $\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$，这是最大值。

在第一次查询中，询问 $l=1, r=3$，Judge 返回 $\operatorname{MEX}([p_1, p_2, p_3])=2$。第二次查询，询问 $l=4, r=4$，Judge 返回 $\operatorname{MEX}([p_4])=0$。类似地，$\operatorname{MEX}([p_1])=1$，$\operatorname{MEX}([p_1, p_2, p_3, p_4])=4$。

通过推理可以得知答案是 $2$。

在第二个样例中，$p=[3,5,0,1,4,2]$。

在第三个样例中，$p=[0,1,2,3]$。

请注意，这些只是交互方式的解释，并未展现任何解题策略。

由 ChatGPT 5 翻译