Xor-Subsequence (hard version)
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.
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$$$.
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.
import sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache, reduce
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, inf
if sys.version >= '3.8':
    from math import comb
RI = lambda : map(int, sys.stdin.buffer.readline().split())
RS = lambda : map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda : list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')
print = lambda d: sys.stdout.write(str(d) + '\n')
MOD = 10 ** 9 + 7
PROBLEM = 'https://codeforces.com/contest/1720/problem/D2\n\n输入 T(≤1e5) 表示 T 组数据。所有数据的 n 之和 ≤3e5。\n每组数据输入 n(2≤n≤3e5) 和长为 n 的数组 a(0≤a[i]≤1e9)，下标从 0 开始。\n\n构造一个严格单调递增的，元素范围在 [0,n-1] 的下标数组 id。\n要求 id 中的所有相邻元素 i 和 j，都满足 a[i] XOR j < a[j] XOR i。\n例如 a=[5,2,4,3,1]，构造 id=[1,2,4]，满足 a[1] XOR 2 < a[2] XOR 1 以及 a[2] XOR 4 < a[4] XOR 2。\n\n输出 id 的最大长度。\n输入\n3\n2\n1 2\n5\n5 2 4 3 1\n10\n3 8 8 2 9 1 6 2 8 3\n输出\n2\n3\n6\n'
''
''

def solve1():
    (n,) = RI()
    a = RILST()
    f = [defaultdict(lambda : [[0] * 2 for _ in range(2)]) for _ in range(30)]
    ans = 0
    for (i, v) in enumerate(a):
        mx = 0
        for k in range(30):
            mx = max(mx, f[k][(v ^ i) >> k + 1][v >> k & 1 ^ 1][i >> k & 1])
        mx += 1
        ans = max(ans, mx)
        for k in range(30):
            p = f[k][(v ^ i) >> k + 1]
            p[i >> k & 1][v >> k & 1] = max(p[i >> k & 1][v >> k & 1], mx)
    print(ans)

def solve2():
    (n,) = RI()
    a = RILST()
    f = [[[{} for _ in range(30)] for _ in range(2)] for _ in range(2)]
    ans = 0
    for (i, v) in enumerate(a):
        mx = 0
        for k in range(30):
            z = f[v >> k & 1 ^ 1][i >> k & 1][k].get((v ^ i) >> k + 1, 0)
            if z > mx:
                mx = z
        mx += 1
        ans = max(ans, mx)
        for k in range(30):
            z = f[i >> k & 1][v >> k & 1][k].get((v ^ i) >> k + 1, 0)
            if mx > z:
                f[i >> k & 1][v >> k & 1][k][(v ^ i) >> k + 1] = mx
    print(ans)

def solve3():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = {}
    for (i, v) in enumerate(a):
        cur = trie
        vi = i ^ v
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if p not in cur:
                cur[p] = {}
            z = cur.get((v >> j & 1 ^ 1) * 2 + (i >> j & 1) + 2, 0)
            if z > f[i]:
                f[i] = z
            cur = cur[p]
        f[i] += 1
        cur = trie
        for j in range(29, -1, -1):
            p = vi >> j & 1
            z = cur.get((i >> j & 1) * 2 + (v >> j & 1) + 2, 0)
            if z < f[i]:
                cur[(i >> j & 1) * 2 + (v >> j & 1) + 2] = f[i]
            cur = cur[p]
    print(max(f))

def solve4():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = [[], [], 0, 0, 0, 0]
    for (i, v) in enumerate(a):
        cur = trie
        vi = i ^ v
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if not cur[p]:
                cur[p] = [[], [], 0, 0, 0, 0]
            z = cur[(v >> j & 1 ^ 1) * 2 + (i >> j & 1) + 2]
            if z > f[i]:
                f[i] = z
            cur = cur[p]
        f[i] += 1
        cur = trie
        for j in range(29, -1, -1):
            p = vi >> j & 1
            z = cur[(i >> j & 1) * 2 + (v >> j & 1) + 2]
            if z < f[i]:
                cur[(i >> j & 1) * 2 + (v >> j & 1) + 2] = f[i]
            cur = cur[p]
    print(max(f))

def solve5():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = [[0, 0] for _ in range(n * 20 + 1)]
    dp = [[0, 0, 0, 0] for _ in range(n * 20 + 1)]
    size = 1
    for (i, v) in enumerate(a):
        vi = i ^ v
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            f[i] = max(f[i], dp[u][(v >> j & 1 ^ 1) * 2 + (i >> j & 1)])
            u = trie[u][p]
            if u == 0:
                break
        f[i] += 1
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if trie[u][p] == 0:
                trie[u][p] = size
                size += 1
            dp[u][(i >> j & 1) * 2 + (v >> j & 1)] = max(dp[u][(i >> j & 1) * 2 + (v >> j & 1)], f[i])
            u = trie[u][p]
    print(max(f))

def solve6():
    (n,) = RI()
    a = RILST()
    f = [0] * n
    trie = [[0] * (n * 30) for _ in range(2)]
    dp = [[0] * (n * 30) for _ in range(4)]
    size = 1
    for (i, v) in enumerate(a):
        vi = i ^ v
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            f[i] = max(f[i], dp[(v >> j & 1 ^ 1) * 2 + (i >> j & 1)][u])
            u = trie[p][u]
            if u == 0:
                break
        f[i] += 1
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if trie[p][u] == 0:
                trie[p][u] = size
                size += 1
            dp[(i >> j & 1) * 2 + (v >> j & 1)][u] = max(dp[(i >> j & 1) * 2 + (v >> j & 1)][u], f[i])
            u = trie[p][u]
    print(max(f))

def solve():
    (n,) = RI()
    a = RILST()
    trie = [[0] * (n * 30) for _ in range(2)]
    dp = [[0] * (n * 30) for _ in range(4)]
    ans = size = 1
    for (i, v) in enumerate(a):
        vi = i ^ v
        f = 0
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            z = dp[(v >> j & 1 ^ 1) << 1 | i >> j & 1][u]
            if z > f:
                f = z
            u = trie[p][u]
            if not u:
                break
        f += 1
        if f > ans:
            ans = f
        u = 0
        for j in range(29, -1, -1):
            p = vi >> j & 1
            if not trie[p][u]:
                trie[p][u] = size
                size += 1
            z = dp[(i >> j & 1) << 1 | v >> j & 1][u]
            if z < f:
                dp[(i >> j & 1) << 1 | v >> j & 1][u] = f
            u = trie[p][u]
    print(ans)
if __name__ == '__main__':
    t = 1
    if t:
        (t,) = RI()
        for _ in range(t):
            solve()
    else:
        solve()
twopow = []
for i in range(30):
    twopow.append(2 ** i)
twopow.reverse()
maxN = int(60000000.0)
trie = [0] * maxN
for i in range(0, maxN, 6):
    trie[i] = trie[i + 1] = -1
idx_of_trie = 6

def get_next_idx_of_trie():
    global idx_of_trie
    idx_of_trie += 6
    return idx_of_trie - 6

def clear_trie():
    global idx_of_trie
    temp = idx_of_trie
    while idx_of_trie >= 1:
        idx_of_trie -= 1
        trie[idx_of_trie] = 0
    for i in range(0, temp, 6):
        trie[i] = trie[i + 1] = -1
    idx_of_trie = 6
bitmap = [(1, 0), (0, 0), (1, 1), (0, 1)]

def main():

    def add(i, ai):
        value = i ^ ai
        node = 0
        currmax = 1
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                if trie[node + 1] == -1:
                    trie[node + 1] = get_next_idx_of_trie()
                neighbour = trie[node]
                node = trie[node + 1]
            else:
                if trie[node] == -1:
                    trie[node] = get_next_idx_of_trie()
                neighbour = trie[node + 1]
                node = trie[node]
            if neighbour != -1:
                (jbit, ajbit) = bitmap[ibit * 2 + aibit]
                currmax = max(currmax, 1 + trie[neighbour + 2 + jbit * 2 + ajbit])
        node = 0
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                node = trie[node + 1]
            else:
                node = trie[node]
            trie[node + 2 + ibit * 2 + aibit] = max(currmax, trie[node + 2 + ibit * 2 + aibit])
        return currmax
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        ans = 0
        for (i, ai) in enumerate(a):
            res = add(i, ai)
            ans = max(ans, res)
        allans.append(ans)
        clear_trie()
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()
twopow = []
for i in range(30):
    twopow.append(2 ** i)
twopow.reverse()
maxN = int(60000000.0)
trie = [0] * maxN
for i in range(0, maxN, 6):
    trie[i] = trie[i + 1] = -1
idx_of_trie = 6

def get_next_idx_of_trie():
    global idx_of_trie
    idx_of_trie += 6
    return idx_of_trie - 6

def clear_trie():
    global idx_of_trie
    temp = idx_of_trie
    while idx_of_trie >= 1:
        idx_of_trie -= 1
        trie[idx_of_trie] = 0
    for i in range(0, temp, 6):
        trie[i] = trie[i + 1] = -1
    idx_of_trie = 6
bitmap = [(1, 0), (0, 0), (1, 1), (0, 1)]

def main():

    def add(i, ai):
        value = i ^ ai
        node = 0
        currmax = 1
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                if trie[node + 1] == -1:
                    trie[node + 1] = get_next_idx_of_trie()
                neighbour = trie[node]
                node = trie[node + 1]
            else:
                if trie[node] == -1:
                    trie[node] = get_next_idx_of_trie()
                neighbour = trie[node + 1]
                node = trie[node]
            if neighbour != -1:
                (jbit, ajbit) = bitmap[ibit * 2 + aibit]
                currmax = max(currmax, 1 + trie[neighbour + 2 + jbit * 2 + ajbit])
        node = 0
        for tp in twopow:
            if i & tp > 0:
                ibit = 1
            else:
                ibit = 0
            if ai & tp > 0:
                aibit = 1
            else:
                aibit = 0
            if value & tp > 0:
                node = trie[node + 1]
            else:
                node = trie[node]
            if currmax > trie[node + 2 + ibit * 2 + aibit]:
                trie[node + 2 + ibit * 2 + aibit] = currmax
        return currmax
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        ans = 0
        for (i, ai) in enumerate(a):
            res = add(i, ai)
            ans = max(ans, res)
        allans.append(ans)
        clear_trie()
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()