You are given a permutation $p$ of integers from $0$ to $n-1$ (each of them occurs exactly once). Initially, the permutation is not sorted (that is, $p_i>p_{i+1}$ for at least one $1 \le i \le n - 1$).

The permutation is called $X$-sortable for some non-negative integer $X$ if it is possible to sort the permutation by performing the operation below some finite number of times:

Choose two indices $i$ and $j$ $(1 \le i \lt j \le n)$ such that $p_i \& p_j = X$.

Swap $p_i$ and $p_j$.

Here $\&$ denotes the bitwise AND operation .

Find the maximum value of $X$ such that $p$ is $X$-sortable. It can be shown that there always exists some value of $X$ such that $p$ is $X$-sortable.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$  — the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer $n$ $(2 \le n \le 2 \cdot 10^5)$  — the length of the permutation.

The second line of each test case contains $n$ integers $p_1, p_2, ..., p_n$ ($0 \le p_i \le n-1$, all $p_i$ are distinct)  — the elements of $p$. It is guaranteed that $p$ is not sorted.

It is guaranteed that the sum of $n$ over all cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case output a single integer — the maximum value of $X$ such that $p$ is $X$-sortable.


-----Examples-----

Input
4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4
Output
2
0
4
1


-----Note-----

In the first test case, the only $X$ for which the permutation is $X$-sortable are $X = 0$ and $X = 2$, maximum of which is $2$.

Sorting using $X = 0$:

Swap $p_1$ and $p_4$, $p = [2, 1, 3, 0]$.

Swap $p_3$ and $p_4$, $p = [2, 1, 0, 3]$.

Swap $p_1$ and $p_3$, $p = [0, 1, 2, 3]$.

Sorting using $X = 2$:

Swap $p_3$ and $p_4$, $p = [0, 1, 2, 3]$.

In the second test case, we must swap $p_1$ and $p_2$ which is possible only with $X = 0$.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Sorting

Constructive algorithms


Solutions:
import sys
input = lambda : sys.stdin.readline().strip()
intput = lambda : map(int, input().split())

def solve():
	(N,) = intput()
	P = [*intput()]
	AND = (1 << 32) - 1
	for (i, x) in enumerate(P):
		if x != i:
			AND &= x
	return AND
(T,) = intput()
for _ in range(T):
	print(solve())


from sys import stdin
from math import log, floor, ceil, gcd
input = stdin.readline
inp = lambda : int(stdin.readline())

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		p = ra(int)
		ans = None
		for i in range(n):
			if i != p[i]:
				if ans == None:
					ans = p[i]
				else:
					ans = ans & p[i]
		print(ans)
main()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	x = 2 ** 20 - 1
	for i in range(n):
		if arr[i] != i:
			x &= arr[i]
	return x
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

def X(numbers, n):
	wrong_numbers = []
	for i in range(n):
		if numbers[i] != i:
			wrong_numbers.append(numbers[i])
	result = wrong_numbers[0]
	for i in range(1, len(wrong_numbers)):
		result = result & wrong_numbers[i]
	return str(result)
t = int(input())
result = ''
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	result += X(numbers, n)
	if i < t - 1:
		result += '\n'
print(result)


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = -1
	for i in range(n):
		if arr[i] != i:
			if ans == -1:
				ans = arr[i]
			else:
				ans = ans & arr[i]
	out += str(ans) + '\n'
print(out)


for s in [*open(0)][2::2]:
	r = ~0
	i = 0
	for x in map(int, s.split()):
		r &= (x, ~0)[x == i]
		i += 1
	print(r)


def main():
	n = int(input())
	for _ in range(n):
		input()
		s = input()
		print(solve(s))

def solve(s):
	nums = [int(num_str) for num_str in s.split()]
	x = 4294967295
	for (i, num) in enumerate(nums):
		if num != i:
			x &= num
	return x
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if a[i] != i:
			ans &= i
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	for i in range(n):
		if a[i] != i:
			ans.append(i)
	for i in range(1, len(ans)):
		ans[0] &= ans[i]
	print(ans[0])
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	andlist = []
	for i in range(n):
		if a[i] != i:
			andlist.append(a[i] & i)
	ans = andlist[0]
	for i in andlist:
		ans &= i
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if s[i] != i:
			if ans == -1:
				ans = i
			else:
				ans &= i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(i) for i in input().strip().split()]
	ans = 524287
	for i in range(n):
		if i != p[i]:
			ans = ans & p[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	for i in range(n):
		if arr[i] != i:
			if flag:
				a &= arr[i]
			else:
				a = arr[i]
				flag = True
	print(a)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	c = 0
	k = -1
	s = [int(i) for i in input().split()]
	for i in range(0, n):
		if s[i] != i:
			k &= s[i]
	print(k)


from math import log2, floor
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 2 ** 32 - 1
	for i in range(n):
		if i == p[i]:
			pass
		else:
			ans &= i
	print(ans)


def findXsortable(n, arr):
	p = 0
	res = -1
	for i in range(0, len(arr)):
		if arr[i] != i:
			if res == -1:
				res = arr[i]
			else:
				res = res & arr[i]
	return res
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	result = findXsortable(n, arr)
	print(result)
	t = t - 1


for it in range(int(input())):
	n = int(input())
	ans = pow(2, 20) - 1
	a = list(map(int, input().split()))
	for i in range(n):
		if a[i] != i:
			ans = ans & i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	res = (1 << 30) - 1
	for i in range(n):
		if l[i] != i:
			res &= l[i]
	print(res)


for u in [*open(0)][2::2]:
	p = ~0
	i = 0
	for x in map(int, u.split()):
		p &= (x, ~0)[x == i]
		i += 1
	print(p)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = -1
	ans = int('1' * 32, 2)
	for i in range(n):
		if i != a[i]:
			ans = ans & a[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	x = -1
	for i in range(n):
		if p[i] != i:
			x &= p[i]
	print(x)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	value = -1
	for i in range(n):
		if i != a[i]:
			value &= a[i]
	print(value)


def solve(n, arr):
	res = []
	for i in range(n):
		if arr[i] != i:
			res.append(i)
	m = (1 << 30) - 1
	for x in res:
		m &= x
	return m
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


from collections import Counter, deque
from collections import OrderedDict, defaultdict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	arr = get.int()
	res = []
	for i in range(n):
		if arr[i] != i:
			res.append(arr[i])
	ans = res[0]
	for i in range(1, len(res)):
		ans = ans & res[i]
	print(ans)
t = int(input())
for tt in range(t):
	solve()


def resi():
	n = int(input())
	p = list(map(int, input().split()))
	x = n
	l = []
	for i in range(n):
		if p[i] != i:
			l.append(i & p[i])
	tmp = l[0]
	for i in range(1, len(l)):
		tmp &= l[i]
	print(tmp)
for _ in range(int(input())):
	resi()


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = (1 << 30) - 1
	for (i, el) in enumerate(p):
		if i != el:
			ans &= el
	print(ans)


def f():
	n = int(input())
	l = list(map(int, input().split()))
	ans = 2 ** 31 - 1 + 2 ** 32
	for i in range(n):
		if i != l[i]:
			ans = ans & l[i]
	print(ans)
t = int(input())
while t:
	f()
	t -= 1


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	x = -1
	for i in range(a):
		if i != b[i]:
			x &= b[i]
	print(x)


for _ in range(int(input())):
	(length, arr) = (int(input()), map(int, input().split(' ')))
	ans = ~0
	for (i, j) in enumerate(arr):
		if i != j:
			ans &= j
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	x = (1 << 30) - 1
	for i in range(n):
		if arr[i] != i:
			x &= arr[i]
	print(x)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if i == l[i]:
			i += 1
		elif ans == -1:
			ans = l[i]
		else:
			ans = ans & l[i]
	print(ans)


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ans = pow(2, 30) - 1
	for k in range(n):
		if li[k] != k:
			ans &= li[k]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	X = -1
	for i in A:
		if A[i] != i:
			if X == -1:
				X = i
			else:
				X = i & X
	print(X)


tc = int(input())
for _ in range(tc):
	n = int(input())
	p = list(map(int, input().split()))
	l = []
	for i in range(len(p)):
		if i != p[i]:
			l += [i & p[i]]
	ans = l[0]
	for i in l:
		ans &= i
	print(ans)


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	ans = -1
	for i in range(a):
		if lis[i] != i:
			ans &= i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	incorrect = []
	for (i, item) in enumerate(a):
		if item != i:
			incorrect.append(item)
	e = incorrect[0]
	for item in incorrect[1:]:
		e &= item
	print(e)


T = int(input())
for _ in range(T):
	l = int(input())
	arr = list(map(int, input().split()))
	ans = None
	for (i, ele) in enumerate(arr):
		if i != ele:
			if ans != None:
				ans = ans & i
			else:
				ans = i
	print(ans)


def solution():
	n = int(input())
	nums = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if nums[i] != i:
			if ans == -1:
				ans = nums[i]
			else:
				ans = ans & nums[i]
	print(ans)
test = int(input())
for _ in range(test):
	solution()


for _ in range(int(input())):
	n = int(input()) - 1
	start = 0
	ms = []
	for i in map(int, input().split()):
		if i == start:
			pass
		else:
			ms.append(i)
		start += 1
	ans = ms[0]
	for x in ms:
		ans &= x
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = list(map(int, input().split()))
	x = -1
	for i in range(n):
		if s[i] != i:
			if x == -1:
				x = s[i]
			else:
				x = x & s[i]
	print(x)


I = input
for _ in range(int(I())):
	n = int(I())
	r = ~0
	for (i, n) in enumerate(map(int, I().split())):
		if n != i:
			r &= n
	print(r)


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	c = []
	for j in range(N):
		if l[j] != j:
			c.append(j)
	A = c[0]
	L = len(c)
	for k in range(1, L):
		A &= c[k]
	print(A)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	ans = 0
	f = 0
	for i in range(n):
		if num[i] != i:
			if f == 0:
				ans = num[i]
				f = 1
			else:
				ans = ans & num[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	ans = 2 ** (n.bit_length() + 1) - 1
	for i in range(n):
		if i != a[i]:
			ans = ans & i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	answ = -1
	for (i, el) in enumerate(a):
		if i != el:
			answ = [el & answ, el][answ == -1]
	print(answ)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = int('1' * 33, 2)
	for i in range(n):
		if l[i] != i:
			ans &= i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	X = int('0b' + '1' * len(bin(n - 1).replace('0b', '')), 2)
	for i in range(n):
		if arr[i] != i:
			X = X & arr[i]
	print(X)


for _ in range(int(input())):
	n = int(input())
	t = [int(x) for x in input().split()]
	ans = 2 ** 20 - 1
	for i in range(n):
		if i != t[i]:
			ans &= t[i]
	print(ans)


t = int(input())
for e in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	q = -1
	for i in range(len(l)):
		if l[i] != i:
			if q == -1:
				q = l[i]
			else:
				q = q & l[i]
		else:
			continue
	print(q)


import sys
input = lambda : sys.stdin.readline().strip()
for Homu in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	ans = -1
	for i in range(n):
		if p[i] != i:
			cond = p[i] & i
			if ans == -1:
				ans = cond
			else:
				ans &= cond
	print(ans)


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	andlist = []
	for i in range(lenn):
		if list1[i] != i:
			andlist.append(i & list1[i])
	ans = andlist[0]
	for i in andlist:
		ans &= i
	print(ans)


for _ in range(int(input())):
	(n, res) = (int(input()), -1)
	A = [int(i) for i in input().split()]
	for i in range(n):
		if A[i] != i:
			if res == -1:
				res = A[i]
			else:
				res &= A[i]
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	ans = []
	for j in range(n):
		if lst[j] != j:
			ans.append(j)
	a = ans[0]
	l = len(ans)
	for j in range(1, l):
		a &= ans[j]
	print(a)


class Solution:

	def solve(self, n, p):
		p1 = sorted(p)
		X = 262143
		for i in range(n):
			if p[i] != p1[i]:
				X = X & p[i]
		return X
T = int(input())
while T:
	T -= 1
	n = int(input())
	p = list(map(int, input().split()))
	print(Solution().solve(n, p))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = (1 << 30) - 1
	for i in range(n):
		if arr[i] != i:
			ans &= arr[i]
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	p = list(map(int, input().split()))
	ind = 0
	x = (1 << n) - 1
	for i in range(n):
		if p[i] == i:
			continue
		else:
			x = x & p[i]
	print(x)
	t = t - 1


for _ in range(int(input())):
	n = int(input()) - 1
	ms = []
	for (i, el) in enumerate(map(int, input().split())):
		if i != el:
			ms.append(el)
	ans = ms[0]
	for x in ms:
		ans &= x
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = (1 << 20) - 1
	for i in range(n):
		if a[i] != i:
			ans &= a[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	m = (1 << 20) - 1
	for (i, p_i) in enumerate(p):
		if i != p_i:
			m &= p_i
	print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = -1
	for i in range(n):
		if i != a[i]:
			if mx == -1:
				mx = a[i]
			else:
				mx = mx & a[i]
	print(mx)


import math as m
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	while l[i] == i:
		i += 1
	ans = l[i]
	while i < n:
		if l[i] != i:
			ans &= l[i]
		i += 1
	print(ans)


t = int(input())
for case in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	for i in range(n):
		if i != d[i]:
			init = i
			break
	result = d[i]
	for i in range(init + 1, n):
		if i != d[i]:
			result = result & d[i]
	print(result)


t = int(input())
for x in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	a = []
	for i in range(n):
		if i != p[i]:
			a.append(p[i])
	ans = a[0]
	for i in range(1, len(a)):
		ans = ans & a[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	List = []
	for i in range(n):
		if A[i] != i:
			List.append(i)
	result = List[0] & List[1]
	for k in range(len(List)):
		result = result & List[k]
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split()
	arr = list(map(int, arr))
	ans = []
	for i in range(len(arr)):
		if i != arr[i]:
			ans.append(arr[i])
	res = ans[0]
	for i in range(len(ans)):
		res = res & ans[i]
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = []
	ans = 1048575
	for i in range(n):
		if arr[i] != i:
			ans &= arr[i]
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	ans = (1 << 20) - 1
	for i in range(n):
		if i != l[i]:
			ans &= l[i]
	print(ans)