CF2106E Wolf

狼发现了 $n$ 只羊，它们的可口度分别为 $p_1, p_2, ..., p_n$，其中 $p$ 是一个排列$^{\text{∗}}$。狼想在 $p$ 上使用二分查找来寻找可口度为 $k$ 的羊，但 $p$ 可能并未排序。对于区间 $[l, r]$ 上寻找 $k$ 的二分查找是否成功，用 $f(l, r, k)$ 表示，其定义如下： 如果 $l > r$，则 $f(l, r, k)$ 失败。否则，令 $m = \lfloor\frac{l + r}{2}\rfloor$，然后： - 如果 $p_m = k$，则 $f(l, r, k)$ 成功； - 如果 $p_m < k$，则 $f(l, r, k) = f(m+1, r, k)$； - 如果 $p_m > k$，则 $f(l, r, k) = f(l, m-1, k)$。 书呆子牛决定帮助狼。书呆子牛会收到 $q$ 个查询，每个查询包含三个整数 $l$、$r$ 和 $k$。在开始查找之前，书呆子牛可以选择一个非负整数 $d$ 和 $d$ 个下标 $1 \le i_1 < i_2 < \ldots < i_d \le n$，其中对于所有 $1 \leq j \leq d$ 都有 $p_{i_j} \neq k$。然后，他可以随意重新排列元素 $p_{i_1}, p_{i_2}, ..., p_{i_d}$。 对于每个查询，输出书呆子牛需要选择的最小整数 $d$，使得 $f(l, r, k)$ 能够成功，或者报告这是不可能的。注意，查询是独立的，且实际的重新排列不会被执行。 $^{\text{∗}}$ 长度为 $n$ 的排列是指包含从 $1$ 到 $n$ 的所有整数且每个整数恰好出现一次的数组。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）——分别表示 $p$ 的长度和查询的数量。 第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$——表示第 $i$ 只羊的可口度。保证 $p$ 中每个从 $1$ 到 $n$ 的整数恰好出现一次。 接下来的 $q$ 行每行包含三个整数 $l$、$r$ 和 $k$（$1 \le l \le r \le n$，$1 \le k \le n$）——分别表示二分查找的区间范围和要查找的整数。 保证所有测试用例的 $n$ 之和和 $q$ 之和均不超过 $2 \cdot 10^5$。

对于每个查询，输出一行，表示书呆子牛需要选择的最小整数 $d$，使得 $f(l, r, k)$ 能够成功。如果不可能，则输出 $-1$。

在第一个样例的第二个查询中：由于 $4$ 不存在于前三个元素中，因此在该范围内查找 $4$ 是不可能的。 在第二个样例的第一个查询中，可以选择下标 $2$ 和 $3$，并交换它们，使得 $p = [3, 5, 1, 2, 7, 6, 4]$。然后，$f(3, 4, 2)$ 的执行过程如下： 1. 令 $m = \lfloor \frac{3 + 4}{2} \rfloor = 3$。因为 $p_3 = 1 < 2$，所以 $f(3, 4, 2) = f(4, 4, 2)$。 2. 令 $m = \lfloor \frac{4 + 4}{2} \rfloor = 4$。因为 $p_4 = 2 = k$，所以 $f(4, 4, 2)$ 成功，因此 $f(3, 4, 2)$ 也成功。 总共选择了 $2$ 个下标，因此最终的成本是 $2$，可以证明这是最小的。注意，对于这个查询，不能选择下标 $4$，因为 $p_4 = k = 2$。 在第二个样例的最后一个查询中，可以选择下标 $2, 3, 4, 5$ 并重新排列它们，使得 $p = [3, 5, 2, 7, 1, 6, 4]$。然后，$f(1, 7, 3)$ 成功。 翻译由 DeepSeek V3 完成