Это сложная версия задачи. Единственное различие состоит в том, что в этой версии \(a_i \le 10^9\).
Дан массив из \(n\) целых чисел \(a_0, a_1, a_2, \ldots a_{n - 1}\). Бряп захотел найти в данном массиве самую длинную хорошую подпоследовательность.
Массив \(b = [b_0, b_1, \ldots, b_{m-1}]\), где \(0 \le b_0 < b_1 < \ldots < b_{m - 1} < n\), будем называть подпоследовательностью длины \(m\) массива \(a\).
Подпоследовательность \(b = [b_0, b_1, \ldots, b_{m-1}]\) длины \(m\) называется хорошей, если выполняется следующее условие:
- Для любого целого числа \(p\) (\(0 \le p < m - 1\)) выполняется условие: \(a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p\).
Здесь \(a \oplus b\) обозначает побитовое исключающее ИЛИ чисел \(a\) и \(b\). Например, \(2 \oplus 4 = 6\), а \(3 \oplus 1=2\).
Так как Бряп не очень любознательная персона, он хочет знать лишь длину такой подпоследовательности. Помогите ему найти ответ на данную задачу.
Примечание
В первом наборе входных данных в качестве подпоследовательности мы можем выбрать оба элемента массива, так как \(1 \oplus 1 < 2 \oplus 0\).
Во втором наборе входных данных мы можем взять элементы с индексами \(1\), \(2\) и \(4\) (в \(0\) нумерации). Для них выполняется: \(2 \oplus 2 < 4 \oplus 1\) и \(4 \oplus 4 < 1 \oplus 2\).