← 返回题目列表

Codeforces · 2093/G

G. 缩短数组

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

长度为 $$$m$$$ 的数组 $$$b$$$ 的美妙之处被定义为 $$$\max(b_i \oplus b_j)$$$ 在所有可能的对 $$$1 \le i \le j \le m$$$ 中,其中 $$$x \oplus y$$$ 是数字 $$$x$$$ 和 $$$y$$$ 的按位异或。我们将数组 $$$b$$$ 的美丽值表示为 $$$f(b)$$$。

如果 $$$f(b) \ge k$$$ 数组 $$$b$$$ 被称为漂亮数组。

最近,Kostya 从商店购买了一个长度为 $$$n$$$ 的数组 $$$a$$$。他认为这个数组太长了,所以他打算从中剪出一些漂亮的子数组。也就是说,他想要选择数字 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 使得数组 $$$a_{l \dots r}$$$ 很漂亮。这样的子数组的长度将是数字$$$r - l + 1$$$。整个数组 $$$a$$$ 也被视为子数组(其中 $$$l = 1$$$ 和 $$$r = n$$$)。

你的任务是找到数组 $$$a$$$ 中最短的美丽子数组的长度。如果没有一个子数组是漂亮的,那么你应该输出数字$$$-1$$$。

输入

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。

接下来,有 $$$t$$$ 两行块:

在块的第一行,有两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$)。

在该块的第二行中,有一个由 $$$n$$$ 整数组成的数组 $$$a$$$ ($$$0 \le a_i \le 10^9$$$)。

保证所有测试的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,您需要输出一个整数 - $$$(l, r)$$$ 段的最小长度,其中 $$$f(a_{l \dots r}) \ge k$$$。如果没有找到这样的段,则应该输出$$$-1$$$。

示例

输入
复制

6
5 0
1 2 3 4 5
5 7
1 2 3 4 5
5 8
1 2 3 4 5
5 7
3 5 1 4 2
5 3
3 5 1 4 2
6 71
26 56 12 45 60 27

输出
复制

1
2
-1
4
2
-1