Красота массива $$$b$$$ длины $$$m$$$ равна $$$\max(b_i \oplus b_j)$$$ среди всевозможных пар $$$1 \le i \le j \le m$$$, где $$$x \oplus y$$$ — это побитовый XOR чисел $$$x$$$ и $$$y$$$. Обозначим значение красоты массива $$$b$$$ как $$$f(b)$$$.
Массив $$$b$$$ называется красивым, если $$$f(b) \ge k$$$.
Недавно Костя купил в магазине массив $$$a$$$ длины $$$n$$$. Он считает этот массив слишком длинным, поэтому он планирует вырезать из него какой-то красивый подотрезок. То есть он хочет выбрать числа $$$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$$$).
Во второй строке блока дан массив $$$a$$$ из $$$n$$$ целых чисел ($$$0 \le a_i \le 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем тестам не превосходит $$$2 \cdot 10^5$$$.
Для каждого теста нужно вывести одно целое число — минимальную длину отрезка $$$(l, r)$$$, для которого $$$f(a_{l \dots r}) \ge k$$$. Если такого отрезка не нашлось, нужно вывести $$$-1$$$.
65 01 2 3 4 55 71 2 3 4 55 81 2 3 4 55 73 5 1 4 25 33 5 1 4 26 7126 56 12 45 60 27
1 2 -1 4 2 -1
| Codeforces Round 1016 (Div. 3) |
|---|
| Закончено |
