codeforces#P1720D2. Xor-Subsequence (hard version)
Xor-Subsequence (hard version)
Description
It is the hard version of the problem. The only difference is that in this version $a_i \le 10^9$.
You are given an array of $n$ integers $a_0, a_1, a_2, \ldots a_{n - 1}$. Bryap wants to find the longest beautiful subsequence in the array.
An array $b = [b_0, b_1, \ldots, b_{m-1}]$, where $0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$, is a subsequence of length $m$ of the array $a$.
Subsequence $b = [b_0, b_1, \ldots, b_{m-1}]$ of length $m$ is called beautiful, if the following condition holds:
- For any $p$ ($0 \le p < m - 1$) holds: $a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$.
Here $a \oplus b$ denotes the bitwise XOR of $a$ and $b$. For example, $2 \oplus 4 = 6$ and $3 \oplus 1=2$.
Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.
The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$) — the length of the array.
The second line of each test case contains $n$ integers $a_0,a_1,...,a_{n-1}$ ($0 \leq a_i \leq 10^9$) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
For each test case print a single integer — the length of the longest beautiful subsequence.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$) — the length of the array.
The second line of each test case contains $n$ integers $a_0,a_1,...,a_{n-1}$ ($0 \leq a_i \leq 10^9$) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
Output
For each test case print a single integer — the length of the longest beautiful subsequence.
Samples
<div class="test-example-line test-example-line-even test-example-line-0">3</div><div class="test-example-line test-example-line-odd test-example-line-1">2</div><div class="test-example-line test-example-line-odd test-example-line-1">1 2</div><div class="test-example-line test-example-line-even test-example-line-2">5</div><div class="test-example-line test-example-line-even test-example-line-2">5 2 4 3 1</div><div class="test-example-line test-example-line-odd test-example-line-3">10</div><div class="test-example-line test-example-line-odd test-example-line-3">3 8 8 2 9 1 6 2 8 3</div><div class="test-example-line test-example-line-odd test-example-line-3"></div>
2
3
6
Note
In the first test case, we can pick the whole array as a beautiful subsequence because $1 \oplus 1 < 2 \oplus 0$.
In the second test case, we can pick elements with indexes $1$, $2$ and $4$ (in $0$ indexation). For this elements holds: $2 \oplus 2 < 4 \oplus 1$ and $4 \oplus 4 < 1 \oplus 2$.