You are given an array A of length N.

Find the maximum length of any subarray of A, such that, the [bitwise OR] of all the elements of the subarray is equal to the [bitwise OR] of the remaining elements of the array. 

Report -1 if no such subarray exists. 

Note:
A subarray is formed by deleting some (possibly zero) elements from the beginning of the array and some (possibly zero) elements from the end of the array.
The bitwise OR of an empty array is considered to be 0.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N — the length of the array A.
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N} representing the array A.

------ Output Format ------ 

For each test case, output on a new line, the length of longest subarray such that the bitwise OR of all elements of the subarray is equal to the bitwise OR of the remaining elements of the array, or output -1 if no such subarray exists. 

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i} < 2^{30}$
- The sum of $N$ over all test cases won't exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
1 2 4
3
1 3 2
4
2 3 4 7

----- Sample Output 1 ------ 
-1
1
3

----- explanation 1 ------ 
Test case $1$: For no subarray of $A$, the bitwise OR of the elements of the subarray equals the bitwise OR of the remaining elements.

Test case $2$: Consider the subarray $[3]$ having length $1$. The bitwise OR of the subarray is $3$ and the bitwise OR of the remaining elements of the array is $1 | 2 = 3$. Thus, the bitwise OR of all elements of the subarray is equal to the bitwise OR of the remaining elements of the array. 

Test case $3$: Consider the subarray $[2, 3, 4]$ having length $3$. The bitwise OR of the subarray is $2|3|4 = 7$ and the bitwise OR of the remaining elements of the array is $7$. Thus, the bitwise OR of all elements of the subarray is equal to the bitwise OR of the remaining elements of the array.

Source: codechef | Difficulty: HARD
Tags: Range queries

Bit manipulation

Mathematics


Solutions:
from collections import Counter, defaultdict
import math
import sys
from collections import Counter
MOD = 10 ** 9 + 7

def readArr():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readStr():
	return input()

def precompute(pat):
	totalLen = len(pat)
	lps = [0 for _ in range(totalLen)]
	length = 0
	i = 1
	while i < totalLen:
		if pat[i] == pat[length]:
			length += 1
			lps[i] = length
			i += 1
		elif length != 0:
			length = lps[length - 1]
		else:
			lps[i] = 0
			i += 1
	return lps

def KMPSearch(pat, text):
	lps = precompute(pat)
	(patLen, textLen) = (len(pat), len(text))
	(i, j) = (0, 0)
	while textLen - i >= patLen - j:
		if text[i] == pat[j]:
			i += 1
			j += 1
		if j == patLen:
			return True
		elif i < textLen and text[i] != pat[j]:
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
	return False

def add_to_map(s, mp):
	for i in range(32):
		if s[i] == '1':
			mp[i] += 1

def remove_from_map(s, mp):
	for i in range(32):
		if s[i] == '1':
			mp[i] -= 1

def compare_map(m1, m2):
	for i in range(32):
		val1 = m1[i] > 0
		val2 = m2[i] > 0
		if val1 != val2:
			return False
	return True

def solve():
	n = readInt()
	arr = readArr()
	x = 0
	not_zero = False
	for val in arr:
		if val != 0:
			not_zero = True
		x = x | val
	if not not_zero:
		print(n)
		return
	strs = [bin(val).replace('0b', '').rjust(32, '0') for val in arr]
	x = bin(x).replace('0b', '').rjust(32, '0')
	cur_map = [0] * 32
	ext_map = [0] * 32
	x_map = [0] * 32
	add_to_map(x, x_map)
	for s in strs:
		add_to_map(s, ext_map)
	if any([val == 1 for val in ext_map]):
		print(-1)
		return
	i = j = 0
	ans = -1
	while j < n and i < n:
		while j < n and (not compare_map(cur_map, x_map)):
			add_to_map(strs[j], cur_map)
			remove_from_map(strs[j], ext_map)
			j += 1
		while j < n and compare_map(ext_map, x_map):
			ans = max(ans, j - i)
			add_to_map(strs[j], cur_map)
			remove_from_map(strs[j], ext_map)
			j += 1
		if compare_map(ext_map, x_map):
			ans = max(ans, j - i)
		remove_from_map(strs[i], cur_map)
		add_to_map(strs[i], ext_map)
		i += 1
	print(ans)
t = readInt()
for test in range(1, t + 1):
	solve()


from bisect import bisect_right
from sys import stdin
input = stdin.readline
MAX = 32

def solve(N, A):
	count = [[0] * (N + 1) for i in range(MAX)]
	for bit in range(MAX):
		for (i, a) in enumerate(A, start=1):
			count[bit][i] = count[bit][i - 1] + (a >> bit & 1)
	for bit in range(MAX):
		if count[bit][N] == 1:
			return -1
	bits = set([bit for bit in range(MAX) if count[bit][N] > 0])
	maximum = 0
	for i in range(1, N + 1):
		if N - i + 1 <= maximum:
			break
		missing = []
		ok = True
		for bit in bits:
			if count[bit][i - 1] == 0:
				missing.append(bit)
			elif count[bit][i - 1] == count[bit][N]:
				ok = False
				break
		if not ok:
			break
		last = N
		for bit in missing:
			if count[bit][last] == count[bit][N]:
				last = bisect_right(count[bit], count[bit][last] - 1) - 1
				if last == i or last - i + 1 <= maximum:
					break
		ok = True
		for bit in bits:
			if count[bit][i - 1] == count[bit][last]:
				ok = False
				break
		if ok:
			maximum = max(maximum, last - i + 1)
			if maximum == N - 1:
				break
	if maximum == 0:
		return -1
	return maximum
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	print(solve(N, A))