Harasees has an array A of size N containing non-negative integers. He starts at the index 1 of A and wants to reach the index N. In one move, he can do the following:
If he is currently at index i, then he can move to any index j such that i ≤ j ≤ \min(i + A_{i}, N). 

The cost of a path is defined as the [bitwise OR] of all the array elements visited by Harasees during his journey from index 1 to N. Formally if he visited the indices 1, X_{1}, X_{2}, \ldots, X_{K}, N, then the cost of this path  = (A_{1} \ | \ A_{X_{1}} \ | \ A_{X_{2}} \ | \ \ldots \ | \ A_{X_{K}} \ | \ A_{N}).

Determine the minimum possible cost to reach index N from index 1. If it is not possible to do so, output -1.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N - the length of the array A.
- The next line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the minimum cost to go from index 1 to index N using the given moves. If it is not possible to do so, output -1.

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

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

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
2
5
1 1 1 1 1
4
2 4 1 3
----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 
- Test Case 1: Harasees has no choice but to keep going from his current position to the position that follows it immediately till he reaches the $5$th index. So the minimum cost (in this case, the only possible cost) is $1\ |\ 1\ |\ 1\ |\ 1\ |\ 1\ =\ 1$.
- Test Case 2: It is optimal for Harasees to make the following moves: $(i = 1) \rightarrow (i = 3) \rightarrow (i = 4)$. The cost of this path is: $A_{1} \ | \ A_{3} \ | \ A_{4} = 2\ |\ 1\ |\ 3\ =\ 3$. We can prove that no path exists with a cost $< 3$.

----- Sample Input 2 ------ 
1
5
1 0 2 3 3
----- Sample Output 2 ------ 
-1
----- explanation 2 ------ 
- Test Case 1: In this case Harasees will get stuck at index $2$ and there is no way to reach the last index.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics

Greedy algorithms


Solutions:
def works(vec, mask):
	if vec[-1] & mask != vec[-1]:
		return False
	mx = 0
	for (i, v) in zip(range(len(vec)), vec):
		if i > mx:
			break
		if v & mask == v and v + i > mx:
			mx = v + i
	return mx >= len(vec) - 1
t = int(input())
for _ in range(t):
	__ = input()
	vec = [int(x) for x in input().split()]
	if not works(vec, (1 << 20) - 1):
		print(-1)
	else:
		ans = 0
		for bit in range(19, -1, -1):
			if not works(vec, ans | (1 << bit) - 1):
				ans |= 1 << bit
		print(ans)


import math

def can_cross(arr, removed, bit):
	length = len(arr)
	reach = 0
	for i in range(length):
		if reach < i:
			return False
		if i not in removed and (not arr[i] & 1 << bit):
			reach = max(reach, i + arr[i])
		if reach >= length:
			return True
	return True
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	maximum_bit = math.ceil(math.log(max(arr), 2))
	removed = set()
	ans = 0
	if can_cross(arr, removed, maximum_bit + 1):
		for j in range(maximum_bit, -1, -1):
			if arr[0] & 1 << j or arr[-1] & 1 << j or (not can_cross(arr, removed, j)):
				ans |= 1 << j
			else:
				for k in range(length):
					if arr[k] & 1 << j:
						removed.add(k)
	else:
		ans = -1
	print(ans)


def check(arr, mask):
	if arr[0] & mask != arr[0]:
		return False
	if arr[-1] & mask != arr[-1]:
		return False
	i = 1
	max_reach = arr[0]
	while i < len(arr):
		if i > max_reach:
			return False
		if arr[i] & mask == arr[i]:
			max_reach = max(max_reach, i + arr[i])
		i += 1
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ans = 0
	for bit in reversed(range(31)):
		if check(arr, ans + (1 << bit) - 1):
			continue
		else:
			ans += 1 << bit
	if check(arr, ans):
		print(ans)
	else:
		print(-1)


from sys import stdin
input = stdin.readline
BIT = 20

def solve(N, A):
	if N == 1:
		return A[0]
	maximum = 1
	i = 1
	while i <= maximum <= N:
		maximum = max(maximum, i + A[i])
		i += 1
	if maximum < N:
		return -1
	answer = 0
	for b in reversed(range(BIT + 1)):
		mask = answer + (1 << b) - 1
		maximum = 1
		if A[1] & mask == A[1] and A[N] & mask == A[N]:
			i = 1
			while i <= maximum and i <= N:
				if A[i] & mask == A[i]:
					maximum = max(maximum, i + A[i])
				i += 1
		if maximum < N:
			answer += 1 << b
	return answer
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [None] + [int(x) for x in input().strip().split()]
	print(solve(N, A))


def check(a, mask):
	if a[0] & mask != a[0]:
		return False
	if a[-1] & mask != a[-1]:
		return False
	reach = a[0]
	for i in range(1, n):
		if i > reach:
			return False
		if a[i] & mask == a[i]:
			reach = max(reach, i + a[i])
	return True
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for bit in reversed(range(21)):
		if check(a, ans + (1 << bit) - 1):
			continue
		else:
			ans += 1 << bit
	if check(a, ans):
		print(ans)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))

	def check(mask):
		if arr[0] | mask != mask:
			return False
		if arr[-1] | mask != mask:
			return False
		dp = [False] * n
		dp[0] = True
		j = 0
		for i in range(n):
			if arr[i] | mask != mask:
				continue
			if not dp[i]:
				continue
			r = min(n - 1, i + arr[i])
			while j <= r:
				if arr[j] | mask == mask:
					dp[j] = True
				j += 1
		return dp[-1]
	mask = (1 << 19) - 1
	if not check(mask):
		print(-1)
	else:
		for i in range(18, -1, -1):
			mask ^= 1 << i
			if not check(mask):
				mask |= 1 << i
		print(mask)


def decToBin(num):
	out = [0 for _ in range(32)]
	idx = 31
	maxBitPos = 31
	while num > 0:
		out[idx] = num % 2
		if num % 2 == 1:
			maxBitPos = idx
		num //= 2
		idx -= 1
	return (out, max(0, maxBitPos - 2))

def binToDec(arr):
	(num, base) = (0, 1)
	for bit in arr[::-1]:
		num += bit * base
		base *= 2
	return num

def isPossible(n, arr):
	(curr, reach) = (0, 0)
	while curr < n and curr <= reach:
		reach = max(reach, curr + arr[curr])
		curr += 1
	return reach >= n - 1

def helper(n, arr, data, ans, k, maxBitPos):
	(curr, reach) = (0, 0)
	while curr < n and curr <= reach:
		isIncluded = True
		for i in range(maxBitPos, k + 1):
			if data[curr][i] == 1 and ans[i] == 0:
				isIncluded = False
		if isIncluded:
			reach = max(reach, curr + arr[curr])
		curr += 1
	return reach >= n - 1

def solve(n, arr):
	if isPossible(n, arr) is False:
		return -1
	data = [None for i in range(n)]
	maxBitPos = 31
	for i in range(n):
		(data[i], bitPos) = decToBin(arr[i])
		maxBitPos = min(maxBitPos, bitPos)
	ans = [0 for _ in range(32)]
	for i in range(32):
		if data[0][i] == 1 or data[-1][i] == 1:
			ans[i] = 1
	for i in range(maxBitPos, 32):
		if ans[i] == 0:
			if helper(n, arr, data, ans, i, maxBitPos) is False:
				ans[i] = 1
	return binToDec(ans)
tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


def canJump(nums):
	n = len(nums)
	i = 0
	while i < n:
		p = i
		if p == n - 1:
			return True
		if nums[p] == 0 and p != n - 1:
			return False
		i += 1
		nxt = i
		m = nums[i]
		while i <= p + nums[p]:
			if i >= n:
				return True
			if m <= nums[i] + (i - p - 1):
				m = nums[i] + (i - p - 1)
				nxt = i
			i += 1
		if nxt == p:
			return False
		i = nxt
	return False
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = arr[0] | arr[-1]
	p = a
	nums = []
	for j in range(n):
		if a | arr[j] == a:
			nums.append(arr[j])
		else:
			nums.append(0)
	if canJump(nums):
		print(a)
		continue
	f = False
	for i in range(20):
		if a >> i & 1 == 0:
			a += 1 << i
			nums = []
			for j in range(n):
				if a | arr[j] == a:
					nums.append(arr[j])
				else:
					nums.append(0)
			if canJump(nums):
				f = True
				idx = i
				break
	if f:
		arr = nums[:]
		for i in range(idx - 1, -1, -1):
			if p >> i & 1 == 0 and a >> i & 1 == 1:
				nums = []
				for j in range(n):
					if arr[j] >> i & 1 == 0:
						nums.append(arr[j])
					else:
						nums.append(0)
				if canJump(nums):
					arr = nums
					a -= 1 << i
		print(a)
	else:
		print(-1)