Given an array A consisting of N integers A_{1},A_{2},…,A_{N}, determine if you can sort this array by applying the following operation several times (possibly, zero):
      
Pick a pair of indices (i,j) with i \neq j and A_{i} \mathbin{\&} A_{j} \neq 0, and swap the values of A_{i} and A_{j}. Here, \mathbin{\&} denotes the [bitwise AND operation].

For example, if A = [6, 4, 2], the two possible operations are (1, 2) and (1, 3). (2, 3) cannot be performed because A_{2} \mathbin{\&} A_{3} = 4 \mathbin{\&} 2 = 0.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}

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

For each test case, output the answer on a new line — YES if the given array can be sorted by repeatedly applying the given operation, and NO otherwise.

You may print each character of the answer string in either uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 3 \cdot 10^{5}$
$0 ≤ A_{i} < 2^{31}$ for each $1 ≤ i ≤ N$
- The sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

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

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
3
6 4 2
6
9 34 4 24 1 6
6
9 34 24 4 1 6
2
1 0
----- Sample Output 1 ------ 
Yes
Yes
No
No
----- explanation 1 ------ 
Test case $1$: $A$ can be sorted by applying the single operation $(1, 3)$.

Test case $2$: $A$ can be sorted by applying the following operations in order: $(1,5), (2,6), (2,3), (4,5)$.

Test cases $3$ and $4$: It can be shown that no sequence of operations will sort $A$.

Source: codechef | Difficulty: VERY_HARD
Tags: Spanning trees

Sorting

Data structures


Solutions:
from collections import defaultdict
t = int(input())
for cas in range(t):
	n = int(input())
	s = input().split()
	nums = [int(i) for i in s]
	ans = True
	bitsets = defaultdict(set)
	bits_unified = defaultdict(set)
	for (idx, num) in enumerate(nums):
		matching_sets = []
		unified_or = num
		for bu in bits_unified:
			if bu & num > 0:
				unified_or |= bu
				matching_sets.append(bu)
		for match in matching_sets:
			del bits_unified[match]
		bits_unified[unified_or] = set()
		for i in range(32):
			if num & 1 << i:
				bitsets[i].add(idx)
	for bu in bits_unified:
		for i in range(32):
			if bu & 1 << i:
				bits_unified[bu] = bits_unified[bu].union(bitsets[i])
	for k in bits_unified:
		bitgroup = bits_unified[k]
		n = len(bitgroup)
		vals = sorted([nums[i] for i in bitgroup])
		indices = sorted([i for i in bitgroup])
		for i in range(n):
			nums[indices[i]] = vals[i]
	ans = True
	for i in range(len(nums) - 1):
		if nums[i] > nums[i + 1]:
			ans = False
			break
	if ans:
		print('Yes')
	else:
		print('No')


from collections import defaultdict as dd
t = int(input())
for s in range(t):
	num = int(input())
	bit = list(map(int, input().split()))
	max = -50
	for i in bit:
		if i > max:
			max = i
	binary = len(bin(max).replace('0b', ''))
	bn = []
	ids = 0
	zds = 0
	for iterable in bit:
		if iterable == 0:
			zds = ids
		b = bin(iterable).replace('0b', '')
		bn.append('0' * (binary - len(b)) + b)
	dp = [[float('inf')] * binary for x in range(num)]
	diff = []
	current = 2
	minimum = current
	for i in range(binary):
		if bn[0][i] == '1':
			dp[0][i] = 1
	for i in range(1, num):
		alter = dd(int)
		for j in range(binary):
			if bn[i][j] == '1':
				minimum = min(minimum, dp[i - 1][j])
				dp[i][j] = minimum
				diff.append(j)
				if dp[i - 1][j] != float('inf'):
					alter[dp[i - 1][j]] = 1
			else:
				dp[i][j] = dp[i - 1][j]
		for k in range(binary):
			if bn[i][k] == '1' or alter[dp[i][k]]:
				dp[i][k] = minimum
		current += 1
		minimum = current
		diff = []
	cy = dd(list)
	for i in range(num):
		for j in range(binary):
			if bn[i][j] == '1':
				cy[dp[-1][j]].append([bit[i], i])
				break
	res = sorted(bit)
	for i in cy:
		values = []
		place = []
		for (j, k) in cy[i]:
			values.append(j)
			place.append(k)
		values.sort()
		t = 0
		for element in values:
			bit[place[t]] = element
			t += 1
	if bit == res:
		print('Yes')
	else:
		print('No')


from collections import defaultdict as dd
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	mx = max(lst)
	bn = len(bin(mx).replace('0b', ''))
	bform = []
	idz = 0
	zid = 0
	for x in lst:
		if x == 0:
			zid = idz
		bf = bin(x).replace('0b', '')
		bform.append('0' * (bn - len(bf)) + bf)
	dp = [[float('inf')] * bn for _ in range(n)]
	curr = 2
	mn = curr
	change = []
	for x in range(bn):
		if bform[0][x] == '1':
			dp[0][x] = 1
	for x in range(1, n):
		changed = dd(int)
		for y in range(bn):
			if bform[x][y] == '1':
				mn = min(mn, dp[x - 1][y])
				dp[x][y] = mn
				change.append(y)
				if dp[x - 1][y] != float('inf'):
					changed[dp[x - 1][y]] = 1
			else:
				dp[x][y] = dp[x - 1][y]
		for z in range(bn):
			if bform[x][z] == '1' or changed[dp[x][z]]:
				dp[x][z] = mn
		curr += 1
		mn = curr
		change = []
	cycles = dd(list)
	for x in range(n):
		for y in range(bn):
			if bform[x][y] == '1':
				cycles[dp[-1][y]].append([lst[x], x])
				break
	rslt = sorted(lst)
	for x in cycles:
		values = []
		adress = []
		for (y, z) in cycles[x]:
			values.append(y)
			adress.append(z)
		values.sort()
		t = 0
		for el in values:
			lst[adress[t]] = el
			t += 1
	print('Yes' if lst == rslt else 'No ')


import time

def solve(N, list):
	if N <= 1:
		return 'Yes'
	masks = {}
	lm = []
	ss = sorted(list)
	for i in range(len(ss) - 1, -1, -1):
		n = ss[i]
		found = False
		for j in range(len(lm)):
			m = lm[j]
			if m & n != 0:
				found = True
				lm[j] |= n
				masks[n] = j
		if not found:
			lm.append(n)
			masks[n] = len(lm) - 1
	for jj in range(N):
		if masks[ss[jj]] != masks[list[jj]]:
			return 'No'
	return 'Yes'
tic = time.perf_counter()
T = int(input())
res = []
for i in range(T):
	N = int(input())
	list = [int(x) for x in input().split()]
	res.append(solve(N, list))
for el in res:
	print(el)
toc = time.perf_counter()


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
sys.setrecursionlimit(10 ** 8)
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353

def get(a):
	if a == par[a]:
		return a
	par[a] = get(par[a])
	return par[a]

def join(a, b):
	a = get(a)
	b = get(b)
	if a == b:
		return
	try:
		par[a] = b
	except:
		pass
for _ in range(ii()):
	n = ii()
	a = il()
	if a == sorted(a):
		print('Yes')
		continue
	par = [i for i in range(n + 1)]
	for i in range(32):
		temp = []
		for j in range(n):
			if a[j] & 1 << i:
				temp.append(j)
		for j in range(1, len(temp)):
			join(temp[j - 1] + 1, temp[j] + 1)
	b = sorted(a)
	d = {}
	for i in range(n):
		if d.get(b[i]):
			d[b[i]].append(i + 1)
		else:
			d[b[i]] = [i + 1]
	val = [[[], []] for i in range(n + 1)]
	for i in range(1, n + 1):
		val[get(i)][0].append(i)
		val[get(i)][1].append(d[a[i - 1]][-1])
		d[a[i - 1]].pop()
	fl = 0
	for i in range(n):
		if sorted(val[i][0]) != sorted(val[i][1]):
			fl = 1
			break
	if fl:
		print('No')
	else:
		print('Yes')


import math

def is_sorted(array, sz):
	if sz == 1:
		return True
	for idx in range(sz - 1):
		if array[idx] > array[idx + 1]:
			return False
	return True

def can_sort(array, sz):
	if is_sorted(array, sz):
		return True
	parent = list(range(sz))

	def union(i, j):
		parent[find(j)] = find(i)
		return

	def find(i):
		if i != parent[i]:
			parent[i] = find(parent[i])
		return parent[i]
	max_digits = int(math.log2(max(array))) + 1
	arr_copy = array[:]
	for dig in range(max_digits):
		first_idx = None
		for idx in range(sz):
			num = arr_copy[idx]
			if num % 2 == 1:
				if first_idx is None:
					first_idx = idx
				else:
					try:
						union(first_idx, idx)
					except Exception:
						pass
			arr_copy[idx] = num // 2
	array_indices = [(num, idx) for (idx, num) in enumerate(array)]
	sorted_array_indices = sorted(array_indices)
	for (orig, fin) in zip(array_indices, sorted_array_indices):
		if find(orig[1]) != find(fin[1]):
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	print('Yes' if can_sort(arr, n) else 'No')


def find(parent, x):
	if parent[x] != x:
		parent[x] = parent[find(parent, parent[x])]
	return parent[x]

def union(parent, rank, length, x, y):
	u = find(parent, x)
	v = find(parent, y)
	if u == v:
		return u
	if rank[u] > rank[v]:
		parent[v] = u
		length[u] += length[v]
		return u
	elif rank[v] > rank[u]:
		parent[u] = v
		length[v] += length[u]
		return v
	if length[u] > length[v]:
		parent[v] = u
		length[u] += length[v]
		rank[u] += 1
		return u
	parent[u] = v
	length[v] += length[u]
	rank[v] += 1
	return v

def setup():
	N = int(input())
	arr = [x for x in map(int, input().split())]
	length = [1] * N
	rank = [1] * N
	parent = list(range(N))
	for ii in range(33):
		i = 0
		while i < N and (not arr[i] & 1 << ii):
			i += 1
		if i < N:
			u = find(parent, i)
			i += 1
			while i < N:
				if arr[i] & 1 << ii:
					v = union(parent, rank, length, u, i)
					if length[v] == N:
						return True
				i += 1
			if length[u] == N:
				return True
	dic = {}
	for i in range(N):
		x = parent[i]
		if x in dic:
			dic[x].append(i)
		else:
			dic[x] = [i]
	for x in dic.values():
		tempU = sorted(list((arr[y] for y in x)))
		for i in range(len(x)):
			arr[x[i]] = tempU[i]
	for i in range(1, N):
		if arr[i - 1] > arr[i]:
			return False
	return True
T = int(input())
for _ in range(T):
	if setup():
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
po = [1]
for i in range(30):
	po.append(2 * po[-1])
while t:
	t -= 1
	n = inp()
	a = lis()
	bits = [set() for i in range(31)]
	for i in range(n):
		for j in range(31):
			if po[j] & a[i]:
				bits[j].add(i)
	for i in range(31):
		for j in range(i + 1, 31):
			common = bits[i].intersection(bits[j])
			if len(common):
				new = set()
				for k in bits[i]:
					new.add(k)
				for k in bits[j]:
					new.add(k)
				bits[i] = {}
				bits[j] = new
				break
	a1 = [0] * n
	for i in range(31):
		new = []
		ind = []
		for j in bits[i]:
			new.append(a[j])
			ind.append(j)
		new.sort()
		ind.sort()
		for j in range(len(ind)):
			a1[ind[j]] = new[j]
	a.sort()
	if a == a1:
		print('Yes')
	else:
		print('No')