You are given N integers \{A_{1}, A_{2}, \ldots, A_{N}\}. Determine whether they can be reordered such that each pair of consecutive differences differ by a factor of 2.

Formally, determine whether there exists a rearrangement of the given integers into an array [B_{1}, B_{2}, \ldots, B_{N}] such that, for each 2 ≤ i ≤ N-1, at least one of the following two conditions holds:
B_{i} - B_{i-1} = 2\cdot (B_{i+1} - B_{i}), *or*
2\cdot (B_{i} - B_{i-1}) = B_{i+1} - B_{i}

Note that different conditions can hold at different indices — the only restriction is that at each index, at least one of the given conditions must hold. Please see the sample tests below for examples.

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

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

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

For each test case, output in a single line the answer — \texttt{YES} if a rearrangement that satisfies the given conditions exists, and \texttt{NO} otherwise.

The output is not case sensitive, so for example the strings \texttt{YES, Yes, yES}, etc. will all be treated as correct. 

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

$1 ≤ T ≤ 100$
$3 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ across all test cases won't exceed $10^{5}$

----- Sample Input 1 ------ 
4
3
5 2 4
5
2 1 16 8 4
5
97 98 100 96 88
6
16 19 18 21 24 22
----- Sample Output 1 ------ 
Yes
Yes
No
Yes

----- explanation 1 ------ 
Test case $1$: Rearrange the numbers to form $[5, 4, 2]$. The consecutive differences are $[4-5, 2-4] = [-1, -2]$, and $-2 = 2\cdot (-1)$.

Test case $2$: One possible rearrangement is $[1, 2, 4, 8, 16]$. The consecutive differences are consecutive powers of $2$.

Test case $3$: No rearrangement of the numbers satisfies the condition. For example, one rearrangement is $[97, 98, 100, 96, 88]$ with consecutive differences $[1, 2, -4, -8]$. $2$ and $-4$ do not differ by a factor of $2$ (they differ by a factor of $-2$), so this is not a valid arrangement.

Source: codechef | Difficulty: EASY
Tags: Sorting

Ad-hoc


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	l = [a[i + 1] - a[i] for i in range(n - 1)]
	c = 0
	for i in range(len(l) - 1):
		if l[i] == 2 * l[i + 1] or l[i] // 2 == l[i + 1] or 2 * l[i] == l[i + 1]:
			c += 1
		else:
			break
	if len(l) - 1 == c:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	for i in range(n - 2):
		if l[i + 2] - l[i + 1] != 2 * (l[i + 1] - l[i]) and l[i + 2] - l[i + 1] != 0.5 * (l[i + 1] - l[i]):
			print('No')
			break
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	f = 1
	for i in range(n - 2):
		if a[i + 1] - a[i] == 2 * (a[i + 2] - a[i + 1]) or 2 * (a[i + 1] - a[i]) == a[i + 2] - a[i + 1]:
			continue
		else:
			f = 0
			print('No')
			break
	if f == 1:
		print('Yes')


for i in range(0, int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = l[::-1]
	h = []
	c = 0
	for i in range(0, len(l) - 1):
		h.append(l[i] - l[i + 1])
	for i in range(len(h) - 1):
		x = h[i]
		y = h[i + 1]
		if x == 2 * y or y == 2 * x:
			c = c + 1
	if c == len(l) - 2:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	k = 0
	for i in range(1, n - 1):
		if l[i] - l[i - 1] != (l[i + 1] - l[i]) * 2 and (l[i] - l[i - 1]) * 2 != l[i + 1] - l[i]:
			k += 1
			break
	if k == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for tc in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	b.sort()
	d = 0
	for i in range(1, n - 1):
		if b[i] - b[i - 1] != 2 * (b[i + 1] - b[i]) and 2 * (b[i] - b[i - 1]) != b[i + 1] - b[i]:
			d += 1
			break
	if d == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ct = 0
	for i in range(1, n - 1):
		if a[i] - a[i - 1] != 2 * (a[i + 1] - a[i]) and 2 * (a[i] - a[i - 1]) != a[i + 1] - a[i]:
			ct = 1
			break
	if ct == 0:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 'NO'
	for i in range(1, len(a) - 1):
		ar = a[i] - a[i - 1]
		b = a[i + 1] - a[i]
		if ar == 2 * b or b == 2 * ar:
			ans = 'Yes'
		else:
			ans = 'No'
			break
	print(ans)


def check(a):
	for k in range(len(a) - 2):
		d = a[k + 1] - a[k]
		e = a[k + 2] - a[k + 1]
		if d != 2 * e and e != 2 * d:
			return 'No'
	return 'Yes'
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	print(check(a))


def check(a):
	for i in range(len(a) - 2):
		b = a[i + 1] - a[i]
		c = a[i + 2] - a[i + 1]
		if b != 2 * c and c != 2 * b:
			return 'No'
	return 'Yes'
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	print(check(a))


def main():
	for _ in range(int(input())):
		n = int(input())
		arr = sorted(list(map(int, input().split(' ')))[:n])
		ans = 'No'
		for i in range(1, n - 1):
			a = arr[i] - arr[i - 1]
			b = arr[i + 1] - arr[i]
			if a == 2 * b or b == 2 * a:
				ans = 'Yes'
			else:
				ans = 'No'
				break
		print(ans)
main()


import sys
R = lambda : map(int, next(sys.stdin).split())
T = int(input())
for i in range(T):
	N = int(input())
	A = list(R())
	A.sort()
	difference = []
	for i in range(1, N):
		difference.append(A[i] - A[i - 1])
	impossible = 0
	for i in range(len(difference) - 1):
		if difference[i] * 2 != difference[i + 1] and difference[i] // 2 != difference[i + 1]:
			impossible = 1
			break
	if impossible == 1:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	b.sort()
	z = 0
	for i in range(1, n - 1):
		if b[i] - b[i - 1] == 2 * (b[i + 1] - b[i]) or 2 * (b[i] - b[i - 1]) == b[i + 1] - b[i]:
			pass
		else:
			z = 1
			break
	if z == 1:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for i in range(1, n - 1):
		if a[i] - a[i - 1] == 2 * (a[i + 1] - a[i]) or a[i] - a[i - 1] == 0.5 * (a[i + 1] - a[i]):
			c += 1
	if c == n - 2:
		print('Yes')
	else:
		print('No')


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	c = 0
	for i in range(1, n - 1):
		if l[i] - l[i - 1] == 2 * (l[i + 1] - l[i]) or 2 * (l[i] - l[i - 1]) == l[i + 1] - l[i]:
			c = 1
		else:
			c = 0
			break
	if c == 0:
		print('No')
	else:
		print('Yes')


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = [int(x) for x in input('').split()]
	k = list(t)
	k.sort()
	c = 'Yes'
	for j in range(1, len(k) - 1):
		d1 = k[j] - k[j - 1]
		d2 = k[j + 1] - k[j]
		if d1 == 2 * d2 or d2 == d1 * 2:
			c = 'Yes'
		else:
			c = 'No'
			break
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = 'Yes'
	for i in range(1, n - 1):
		x = a[i] - a[i - 1]
		y = a[i + 1] - a[i]
		if x == 2 * y or y == 2 * x:
			c = 'Yes'
		else:
			c = 'No'
			break
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	t = True
	for i in range(1, n - 1):
		if l[i] - l[i - 1] != 2 * (l[i + 1] - l[i]):
			if 2 * (l[i] - l[i - 1]) != l[i + 1] - l[i]:
				t = False
	if not t:
		l.sort(reverse=True)
		if l[i] - l[i - 1] != 2 * (l[i + 1] - l[i]):
			if 2 * (l[i] - l[i - 1]) != l[i + 1] - l[i]:
				t = False
	if t:
		print('Yes')
	else:
		print('No')


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	flag = True
	for i in range(2, n - 1):
		x = A[i] - A[i - 1]
		y = A[i + 1] - A[i]
		if 2 * x != y and x != 2 * y:
			flag = False
			break
	if flag:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	diffs = []
	for i in range(len(arr) - 1):
		diffs.append(arr[i] - arr[i + 1])
	valid = True
	for i in range(len(diffs) - 1):
		if not (diffs[i + 1] == diffs[i] * 2 or diffs[i + 1] == diffs[i] / 2):
			valid = False
			break
	if valid:
		print('Yes')
	else:
		print('No')


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	flag = 1
	for i in range(n - 2):
		curdif = a[i + 1] - a[i]
		nexdif = a[i + 2] - a[i + 1]
		if curdif == 2 * nexdif or 2 * curdif == nexdif:
			continue
		else:
			flag = 0
			break
	if flag == 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	if l[-2] - l[-3] == 2 * (l[-1] - l[-2]) or 2 * (l[-2] - l[-3]) == l[-1] - l[-2]:
		print('Yes')
	else:
		print('No')


def check(A, n):
	for i in range(1, n - 1):
		if A[i + 1] - A[i] != (A[i] - A[i - 1]) * 2 and (A[i + 1] - A[i]) * 2 != A[i] - A[i - 1]:
			print('No')
			return 0
	print('Yes')
for _ in range(int(input())):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	check(A, n)


n = int(input())
numbers = []
for i in range(n):
	input()
	numbers.append(list(map(int, input().split())))

def answer(l):
	a = sorted(l)
	previousDifference = a[1] - a[0]
	for i in range(1, len(a) - 1):
		newDifference = a[i + 1] - a[i]
		if newDifference != 2 * previousDifference and newDifference != previousDifference * 0.5:
			return 'No'
		previousDifference = newDifference
	return 'Yes'
for i in numbers:
	print(answer(i))


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	if lst[-2] - lst[-3] == 2 * (lst[-1] - lst[-2]) or 2 * (lst[-2] - lst[-3]) == lst[-1] - lst[-2]:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	flag = True
	for i in range(1, n - 1):
		if A[i] - A[i - 1] != 2 * (A[i + 1] - A[i]) and A[i] - A[i - 1] != 0.5 * (A[i + 1] - A[i]):
			flag = False
	if flag:
		print('Yes')
	else:
		print('No')


def solve(n, lst):
	lst.sort()
	f = 0
	for i in range(1, n - 1):
		t1 = lst[i] - lst[i - 1]
		t2 = lst[i + 1] - lst[i]
		if t1 * 2 == t2 or t2 * 2 == t1:
			f = 1
		else:
			f = 0
			break
	print('Yes' if f == 1 else 'No')
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	solve(n, lst)


for _ in range(int(input())):
	N = int(input())
	A = sorted(list(map(int, input().split())))
	for i in range(1, N - 1):
		x = abs(A[i] - A[i - 1])
		y = abs(A[i + 1] - A[i])
		if x != 2 * y and y != 2 * x:
			print('No')
			break
	else:
		print('Yes')


def check(li, n):
	for i in range(2, n - 1):
		if li[i] - li[i - 1] != 2 * (li[i + 1] - li[i]) and 2 * (li[i] - li[i - 1]) != li[i + 1] - li[i]:
			return 'No'
	return 'Yes'
t = int(input())
while t:
	n = int(input())
	li = []
	for i in input().split():
		li.append(int(i))
	li.sort()
	print(check(li, n))
	t -= 1


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	c = 0
	for i in range(1, n - 1):
		if A[i] - A[i - 1] != 2 * (A[i + 1] - A[i]) and 2 * (A[i] - A[i - 1]) != A[i + 1] - A[i]:
			break
		else:
			c += 1
	if c == n - 2:
		print('Yes')
	else:
		print('No')


T = int(input())
R = []
for _ in range(T):
	N = int(input())
	A = list(map(int, input().strip().split()))
	A.sort(reverse=True)
	flag = True
	for i in range(1, N - 1):
		if A[i] - A[i - 1] != 2 * (A[i + 1] - A[i]) and 2 * (A[i] - A[i - 1]) != A[i + 1] - A[i]:
			flag = False
			break
	if flag:
		R.append('Yes')
	else:
		R.append('No')
for r in R:
	print(r)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	count = 0
	for i in range(1, N - 1):
		if A[i] - A[i - 1] == 2 * (A[i + 1] - A[i]) or 2 * (A[i] - A[i - 1]) == A[i + 1] - A[i]:
			count += 1
		else:
			pass
	if count == N - 2:
		print('Yes')
	else:
		print('No')


t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=False)
	flg = 0
	a = 0
	b = 0
	for i in range(2, n - 1):
		a = arr[i] - arr[i - 1]
		b = arr[i + 1] - arr[i]
		if 2 * a != b and 2 * b != a:
			flg = 1
			break
	if flg:
		print('No')
	else:
		print('Yes')
	t = t - 1