У вас есть массив целых неотрицательных чисел \(a_1, a_2, \ldots, a_n\).
Значение подотрезка длины \(\ge 2\): \(a[l, r] = [a_l, a_{l+1}, \ldots, a_r]\) — это минимальное значение \(a_i \oplus a_j\) такое, что \(l \le i < j \le r\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Вам нужно найти \(k\)-е наименьшее значение среди всех подотрезков длины \(\ge 2\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(k\)-ю порядковую статистику среди значений всех подотрезков длины хотя бы \(2\).
Примечание
В первом наборе входных данных мы имеем такие подотрезки и наименьшие значения побитового исключающего ИЛИ пары элементов:
\([1,2]: 3\)
\([2,3]: 1\)
\([3,4]: 7\)
\([4,5]: 1\)
\([1,2,3]: 1\)
\([2,3,4]: 1\)
\([3,4,5]: 1\)
\([1,2,3,4]: 1\)
\([2,3,4,5]: 1\)
\([1,2,3,4,5]: 1\)
Упорядоченные значения: \(1, 1, 1, 1, 1, 1, 1, 1, 3, 7\). Таким образом, вторым наименьшим элементом будет \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2
1 2 3 4 5
2 1
4 3
4 6
1 2 4 8
5 9
1 2 3 4 5
|
1
7
12
3
|