Wolf 找到了 $$$n$$$ 羊,其美味值为 $$$p_1, p_2, ..., p_n$$$,其中 $$$p$$$ 是排列 $$$^{\text{*}}$$$。 Wolf想对$$$p$$$进行二分查找,找到味道为$$$k$$$的羊,但$$$p$$$不一定是排序的。在 $$$[l, r]$$$ 范围内对 $$$k$$$ 成功进行二分查找表示为 $$$f(l, r, k)$$$,其定义如下:
如果 $$$l \gt r$$$,则 $$$f(l, r, k)$$$ 失败。否则,设 $$$m = \lfloor\frac{l + r}{2}\rfloor$$$,并且:
- 如果 $$$p_m = k$$$,则 $$$f(l, r, k)$$$ 为 成功,
- 如果 $$$p_m \lt k$$$,则 $$$f(l, r, k) = f(m+1, r, k)$$$,
- 如果 $$$p_m \gt k$$$,则 $$$f(l, r, k) = f(l, m-1, k)$$$。
书呆子牛决定帮助狼。 Cow the Nerd 被给予 $$$q$$$ 查询,每个查询由三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ 组成。在搜索开始之前,Cow the Nerd 可以选择一个非负整数 $$$d$$$ 和 $$$d$$$ 索引 $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_d \le n$$$,其中 $$$p_{i_j} \neq k$$$ 在所有 $$$1 \leq j \leq d$$$ 上。然后,他可以按照自己的喜好对元素 $$$p_{i_1}, p_{i_2}, ..., p_{i_d}$$$ 重新排序。
对于每个查询,输出 最小值 书呆子 Cow 必须选择的整数 $$$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$$$ 只羊的美味程度。保证从 $$$1$$$ 到 $$$n$$$ 的每个整数在 $$$p$$$ 中恰好出现一次。
以下 $$$q$$$ 行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ $$$(1 \le l \le r \le n, 1 \le k \le n)$$$ — 将执行二分搜索的范围以及每个查询搜索的整数。
保证所有情况下 $$$n$$$ 的总和与 $$$q$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,输出 Cow the Nerd 必须选择的最小整数 $$$d$$$,以便 $$$f(l, r, k)$$$ 在新行上成功。如果不可能,则输出$$$-1$$$。
示例
输入复制
85 31 2 3 4 51 5 41 3 43 4 47 43 1 5 2 7 6 43 4 22 3 51 5 61 7 32 12 11 2 11 111 1 17 13 4 2 5 7 1 61 7 116 116 10 12 6 13 9 14 3 8 11 15 2 7 1 5 41 16 416 114 1 3 15 4 5 6 16 7 8 9 10 11 12 13 21 16 1413 112 13 10 9 8 4 11 5 7 6 2 1 31 13 2
输出复制
0 -1 0 2 0 -1 4 -1 0 -1 -1 -1 -1
注意
在第一个例子中,第二个查询:由于$$$4$$$在前三个元素中不存在,因此在该范围内搜索时不可能找到它。
在第二个示例中,在第一个查询中,您可以选择索引 $$$2$$$、$$$3$$$,并将它们交换为 $$$p = [3, 5, 1, 2, 7, 6, 4]$$$。然后,$$$f(3, 4, 2)$$$ 将按如下方式工作:
- 令 $$$m = \lfloor \frac{3 + 4}{2} \rfloor = 3$$$。因为 $$$p_3 = 1 \lt 2$$$,所以 $$$f(3, 4, 2) = f(4, 4, 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)$$$ 就成功了。