Alice has a cake, and she is going to cut it. She will perform the following operation $n-1$ times: choose a piece of the cake (initially, the cake is all one piece) with weight $w\ge 2$ and cut it into two smaller pieces of weight $\lfloor\frac{w}{2}\rfloor$ and $\lceil\frac{w}{2}\rceil$ ($\lfloor x \rfloor$ and $\lceil x \rceil$ denote floor and ceiling functions , respectively).

After cutting the cake in $n$ pieces, she will line up these $n$ pieces on a table in an arbitrary order. Let $a_i$ be the weight of the $i$-th piece in the line.

You are given the array $a$. Determine whether there exists an initial weight and sequence of operations which results in $a$.


-----Input-----

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

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

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

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


-----Output-----

For each test case, print a single line: print YES if the array $a$ could have resulted from Alice's operations, otherwise print NO.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).


-----Examples-----

Input
14
1
327
2
869 541
2
985214736 985214737
3
2 3 1
3
2 3 3
6
1 1 1 1 1 1
6
100 100 100 100 100 100
8
100 100 100 100 100 100 100 100
8
2 16 1 8 64 1 4 32
10
1 2 4 7 1 1 1 1 7 2
10
7 1 1 1 3 1 3 3 2 3
10
1 4 4 1 1 1 3 3 3 1
10
2 3 2 2 1 2 2 2 2 2
4
999999999 999999999 999999999 999999999
Output
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES


-----Note-----

In the first test case, it's possible to get the array $a$ by performing $0$ operations on a cake with weight $327$.

In the second test case, it's not possible to get the array $a$.

In the third test case, it's possible to get the array $a$ by performing $1$ operation on a cake with weight $1\,970\,429\,473$:

Cut it in half, so that the weights are $[985\,214\,736, 985\,214\,737]$.

Note that the starting weight can be greater than $10^9$.

In the fourth test case, it's possible to get the array $a$ by performing $2$ operations on a cake with weight $6$:

Cut it in half, so that the weights are $[3,3]$.

Cut one of the two pieces with weight $3$, so that the new weights are $[1, 2, 3]$ which is equivalent to $[2, 3, 1]$ up to reordering.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Data structures

Implementation

Greedy algorithms


Solutions:
import sys
import math
from bisect import bisect_right as br
from collections import deque, Counter
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()

def check(val):
	if track[val] > 0:
		track[val] -= 1
		return 1
	if val == 1:
		return 0
	return check(val // 2) and check((val + 1) // 2)
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	track = Counter(arr)
	if check(sum(arr)):
		print('YES')
	else:
		print('NO')


from collections import Counter
tests = int(input())
results = []

def pedacoPossivel(tamanhoBolo):
	if boloCounter[tamanhoBolo]:
		boloCounter[tamanhoBolo] -= 1
		return True
	return tamanhoBolo > 1 and pedacoPossivel(tamanhoBolo // 2) and pedacoPossivel(tamanhoBolo - tamanhoBolo // 2)
for a in range(tests):
	numeroPedacos = int(input())
	pedacos = [int(t) for t in input().split()]
	boloCounter = Counter(pedacos)
	tamanhoBolo = sum(pedacos)
	if pedacoPossivel(tamanhoBolo):
		results.append('YES')
	else:
		results.append('NO')
for r in results:
	print(r)


import sys
input = sys.stdin.readline
from collections import deque

def solve(n, arr):
	count = {}
	for num in arr:
		if num not in count:
			count[num] = 0
		count[num] += 1
	S = sum(arr)
	q = deque([S])
	cnt = n - 1
	while q and cnt >= 0:
		node = q.popleft()
		if node in count and count[node] > 0:
			count[node] -= 1
			continue
		val1 = node // 2 + node % 2
		val2 = node // 2
		cnt -= 1
		q.append(val1)
		q.append(val2)
	if cnt == 0 and len(q) == 0 and all([count[key] == 0 for key in count]):
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


from collections import defaultdict

def solve(x, d):
	if d[x] > 0:
		d[x] -= 1
		return True
	if x == 1:
		return False
	return solve(x // 2, d) and solve((x + 1) // 2, d)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = defaultdict(int)
	sum_1 = 0
	for i in a:
		f[i] += 1
		sum_1 += i
	if solve(sum_1, f):
		print('YES')
	else:
		print('NO')


from collections import Counter

def solve(x, d):
	if d[x] > 0:
		d[x] -= 1
		return True
	if x == 1:
		return False
	return solve(x // 2, d) and solve((x + 1) // 2, d)
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = Counter(arr)
	sm = sum(arr)
	ans = solve(sm, d)
	print('YES') if ans else print('NO')


from collections import Counter

def f(s):
	if d[s]:
		d[s] -= 1
		return True
	return s > 1 and f(s // 2) and f(s - s // 2)
for a in [0] * int(input()):
	input()
	r = [*map(int, input().split())]
	d = Counter(r)
	print('NYOE S'[f(sum(r))::2])


def solve():
	n = int(input())
	a = []
	counts = {}
	for x in input().split():
		x = int(x)
		a.append(x)
		counts.setdefault(x, 0)
		counts[x] += 1
	initial = sum(a)
	stop = min(a)
	unwanted = [initial]
	while unwanted != []:
		sl = unwanted.pop(0)
		if sl in counts and counts[sl] > 0:
			counts[sl] -= 1
		else:
			(w, y) = (sl // 2, sl // 2 + sl % 2)
			if w < stop:
				print('NO')
				return
			unwanted = [w, y] + unwanted
	print('YES')
for tc in range(int(input())):
	solve()


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	s = sum(l)

	def solve(x):
		if x in c and c[x] > 0:
			c[x] -= 1
			return True
		elif x == 1:
			return False
		else:
			return solve(x // 2) and solve((x + 1) // 2)
	if solve(s):
		print('YES')
	else:
		print('NO')


import heapq
_ = int(input())
for i in range(_):
	n = int(input())
	a = list(map(int, input().split()))
	dic = {}
	for i in a:
		if i not in dic:
			dic[i] = 0
		dic[i] += 1
	s = sum(a)
	cs = [0]

	def dfs(x):
		if x <= 1:
			if x not in dic:
				dic[x] = 0
			dic[x] -= 1
			return
		if x in dic and dic[x] > 0:
			dic[x] -= 1
			return
		else:
			t1 = x // 2
			t2 = x - t1
			cs[0] += 1
			if cs[0] < n:
				dfs(t1)
				dfs(t2)
			else:
				dic[-1] = -1
				return
	dfs(s)
	ans = 'YES'
	for i in dic:
		if dic[i] != 0:
			ans = 'NO'
	print(ans)


import heapq
from math import ceil, floor
R = lambda : map(int, input().split())
arr = []
d = dict()

def tes(t):
	if not t:
		return False
	if t in d and d[t]:
		d[t] -= 1
		return True
	return tes(floor(t / 2)) and tes(ceil(t / 2))
(t,) = R()
for _ in range(t):
	(n,) = R()
	arr = list(R())
	d = dict()
	for k in arr:
		d[k] = d.get(k, 0) + 1
	print('YES' if tes(sum(arr)) else 'NO')


from collections import Counter
testCases = int(input())

def check(value):
	if count[value] > 0:
		count[value] -= 1
		return True
	if value == 1:
		return False
	return check(value // 2) and check((value + 1) // 2)
for _ in range(testCases):
	n = int(input())
	q = [int(x) for x in input().split()]
	count = Counter(q)
	if check(sum(q)):
		print('YES')
	else:
		print('NO')


from collections import Counter

def solve(s):
	if C[s]:
		C[s] -= 1
		return True
	return s > 1 and solve(s // 2) and solve(s - s // 2)
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	C = Counter(L)
	s = sum(L)
	if solve(s):
		print('YES')
	else:
		print('NO')


def ANS(y, d):
	if d[y] > 0:
		d[y] -= 1
		return True
	if y == 1:
		return False
	return ANS(y // 2, d) and ANS((y + 1) // 2, d)
import math
from collections import Counter
for k in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	s = sum(A)
	d = Counter(A)
	ans = ANS(s, d)
	if ans:
		print('YES')
	else:
		print('NO')


import heapq as hq
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	q = [-sum(a)]
	flag = 0
	while a:
		v = -hq.heappop(q)
		if v == a[-1]:
			a.pop()
		elif v < a[-1]:
			print('NO')
			flag = 1
			break
		else:
			hq.heappush(q, -(v // 2))
			hq.heappush(q, -((v + 1) // 2))
	if flag == 0:
		print('YES')


from math import ceil, floor
map_counts = {}

def can_i_slice_it(tot):
	if tot == 0:
		return False
	if map_counts.get(tot, False):
		map_counts[tot] -= 1
		return True
	return can_i_slice_it(floor(tot / 2)) and can_i_slice_it(ceil(tot / 2))

def value_counts(array):
	a = {}
	for i in array:
		a[i] = a.get(i, 0) + 1
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split(' ')
	a = list(map(lambda x: int(x), a))
	map_counts = value_counts(a)
	tot = sum(a)
	if can_i_slice_it(tot):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	pieces = [sum(a)]
	frequency = {}
	for i in a:
		frequency[i] = frequency.get(i, 0) + 1
	operation = 0
	while pieces and operation < n:
		piece = pieces.pop()
		if frequency.get(piece):
			frequency[piece] -= 1
			continue
		pieces.append(piece // 2)
		pieces.append((piece + 1) // 2)
		operation += 1
	print('YES') if operation == n - 1 else print('NO')


import collections
T = int(input())
for _ in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	count = collections.Counter(nums)
	q = collections.deque([sum(nums)])
	if N == 1:
		print('YES')
		continue
	divide = N - 1
	while q and divide > 0:
		divide -= 1
		num = q.popleft()
		if num == 1:
			continue
		num1 = num2 = num // 2
		if num % 2 == 1:
			num2 += 1
		if count[num1] > 0:
			count[num1] -= 1
			N -= 1
		else:
			q.append(num1)
		if count[num2] > 0:
			count[num2] -= 1
			N -= 1
		else:
			q.append(num2)
	if N == 0:
		print('YES')
	else:
		print('NO')


import heapq
import math

def solve(s):
	n = len(s)
	s.sort(reverse=True)
	d = dict()
	total = sum(s)
	h = []
	heapq.heappush(h, -total)
	for c in s:
		curr_max = total
		while c < curr_max:
			curr_max = -heapq.heappop(h)
			if c == curr_max:
				continue
			elif c < curr_max:
				heapq.heappush(h, math.ceil(-curr_max / 2))
				heapq.heappush(h, math.floor(-curr_max / 2))
			else:
				print('NO')
				return
	print('YES')
	return
test = int(input())
for te in range(0, test):
	n = int(input())
	s = list(map(int, input().split()))
	solve(s)


import math
t = int(input())
res = []
for _ in range(t):
	input()
	a = [int(x) for x in input().split(' ')]
	(d, s) = ({}, 0)
	for v in a:
		s += v
		if v in d:
			d[v] += 1
		else:
			d[v] = 1
	(lst, count) = ([s], 0)
	while lst and count < len(a):
		cur = lst.pop()
		if cur in d:
			d[cur] -= 1
			if d[cur] == 0:
				del d[cur]
		else:
			count += 1
			if cur % 2:
				lst.append(math.ceil(cur / 2))
			else:
				lst.append(cur // 2)
			lst.append(cur // 2)
	if lst:
		res.append(False)
	else:
		res.append(True)
for i in range(t):
	if res[i]:
		print('YES')
	else:
		print('NO')


from collections import Counter, defaultdict, deque, namedtuple
from email.policy import default
from functools import lru_cache
from typing import List, Dict
import bisect as b
import heapq as h
import math as m

def ints():
	return [int(x) for x in input().split()]

def main_tc():
	n = int(input())
	pieces = ints()
	total = 0
	for piece in pieces:
		total += piece
	counter = defaultdict(int)
	for piece in pieces:
		counter[piece] += 1
	queue = deque()
	queue.append(total)
	cut = 0
	while len(queue) > 0:
		if cut == n:
			print('NO')
			return
		piece = queue.popleft()
		if counter[piece] > 0:
			counter[piece] -= 1
			continue
		cut += 1
		p1 = piece // 2
		p2 = piece // 2 + piece % 2
		queue.append(p1)
		queue.append(p2)
	print('YES')

def main():
	tc = int(input())
	for _ in range(tc):
		main_tc()
main()


from collections import Counter

def solve(n):
	(s, n) = (Counter(n), [sum(n)])
	while s:
		t = n[-1]
		if 0 in n:
			return False
		elif t in s:
			if s[t] == 1:
				s.pop(t)
			else:
				s[t] -= 1
		else:
			n.append(t + 1 >> 1)
			n.append(t >> 1)
		n.remove(t)
	return True
for i in range(int(input())):
	int(input())
	print('YES' if solve([int(i) for i in input().split()]) else 'NO')


from collections import defaultdict
import math
t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print('YES')
	else:
		total = 0
		d = {}
		for x in arr:
			total += x
			try:
				d[x] += 1
			except:
				d[x] = 1
		q = [total]
		while len(q) < n:
			x = q.pop()
			(a, b) = (x // 2, x - x // 2)
			if a in d:
				d[a] -= 1
				n -= 1
				if d[a] == 0:
					del d[a]
			else:
				q.append(a)
			if b in d:
				d[b] -= 1
				n -= 1
				if d[b] == 0:
					del d[b]
			else:
				q.append(b)
		if len(q) == 0:
			print('YES')
		else:
			print('NO')


import heapq as h
from collections import Counter

def solve(n: list) -> bool:
	s = Counter(n)
	n = [sum(n)]
	while s:
		if (t := n[0]) == 0:
			return False
		elif t in s:
			if s[t] == 1:
				s.pop(t)
			else:
				s[t] -= 1
			h.heappop(n)
		else:
			h.heapreplace(n, t >> 1)
			h.heappush(n, t + 1 >> 1)
	return True

def go() -> None:
	for i in range(int(input())):
		int(input())
		print('YES' if solve([int(i) for i in input().split()]) else 'NO')
go()


import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	final = []
	heapq.heappush(final, -1 * sum(arr))
	i = 0
	while i < n:
		cur = heapq.heappop(final) * -1
		if cur > arr[i]:
			a = cur // 2
			b = cur - a
			heapq.heappush(final, -1 * a)
			heapq.heappush(final, -1 * b)
		elif cur == arr[i]:
			i += 1
		else:
			break
	print('YES' if i == n else 'NO')


import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	init = sum(a)
	vis = {}
	for i in a:
		if i not in vis:
			vis[i] = 1
		else:
			vis[i] += 1
	que = [init]
	while que:
		temp = que.pop()
		if temp in vis and vis[temp] > 0:
			vis[temp] -= 1
		else:
			if temp == 1:
				break
			que.append(temp // 2)
			que.append((temp + 1) // 2)
	ans = 'YES'
	for i in vis:
		if vis[i] > 0:
			ans = 'NO'
			break
	print(ans)


from collections import Counter

def cal():
	q = [tot]
	i = 0
	while q and i < n:
		k = q.pop()
		if k in c:
			c[k] -= 1
			if c[k] == 0:
				del c[k]
			continue
		if k == 1:
			return False
		if k % 2 == 0:
			q += [k // 2, k // 2]
		else:
			q += [k // 2, k // 2 + 1]
		i += 1
	if len(c) == 0:
		return True
	return False
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	c = Counter(arr)
	tot = sum(arr)
	if cal():
		print('YES')
	else:
		print('NO')


import math as m
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	s = sum(lst)
	a_dict = {}
	for i in lst:
		a_dict[i] = 1 if i not in a_dict else a_dict[i] + 1
	ans = [s]
	pos = True
	while ans:
		x = ans.pop()
		if x == 0:
			pos = False
			break
		if x in a_dict:
			a_dict[x] -= 1
			if a_dict[x] == 0:
				a_dict.pop(x)
		else:
			ans += [m.ceil(x / 2), m.floor(x / 2)]
	print('YES' if pos else 'NO')


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
from collections import defaultdict
for _ in range(I()):
	n = I()
	arr = L()
	if n == 1:
		print('YES')
		continue
	sm = 0
	C = defaultdict(int)
	for i in range(len(arr)):
		C[arr[i]] += 1
		sm += arr[i]
	sums = [sm]
	cnt = 0
	while sums:
		p = sums.pop()
		(a, b) = (p // 2, p - p // 2)
		if a == 0 or b == 0:
			break
		if C[a] > 0:
			C[a] -= 1
			cnt += 1
		else:
			sums.append(a)
		if C[b] > 0:
			C[b] -= 1
			cnt += 1
		else:
			sums.append(b)
		if cnt >= n:
			break
	flag = 1
	for e in C:
		if C[e] > 0:
			flag = 0
			break
	if flag:
		print('YES')
	else:
		print('NO')


import heapq
from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	a.sort(reverse=True)
	h = []
	heapq.heappush(h, s * -1)
	i = 0
	flag = True
	while i < n:
		x = heapq.heappop(h) * -1
		if x == a[i]:
			i += 1
		elif x > a[i]:
			heapq.heappush(h, ceil(x / 2) * -1)
			heapq.heappush(h, x // 2 * -1)
		else:
			flag = False
			break
	if flag:
		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()))
	cake = 0
	dk = dd(int)
	for x in lst:
		dk[x] += 1
		cake += x
	queue = [cake]
	cut = 0
	while queue and cut < n:
		piece = queue.pop()
		if dk[piece]:
			dk[piece] -= 1
			continue
		queue.append(piece // 2)
		queue.append(piece // 2 + piece % 2)
		cut += 1
	if cut == n - 1:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	a = sum(l)
	lk = [a]
	d = {}
	b = min(l)
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	while len(lk) > 0:
		a = lk[0]
		(p, q) = (a // 2, a // 2 + a % 2)
		if a in d and d[a] > 0:
			d[a] -= 1
			del lk[0]
		elif p < b:
			print('NO')
			break
		else:
			del lk[0]
			lk = [p, q] + lk
	else:
		print('YES')


import heapq
from collections import Counter
import math

def ans(n, l, c):
	if n == 1:
		return 'YES'
	heap = [-sum(l)]
	heapq.heapify(heap)
	while len(heap) < n:
		x = heapq.heappop(heap)
		y = math.floor(x / 2) * -1
		z = math.ceil(x / 2) * -1
		if c[z]:
			c[z] -= 1
			n -= 1
		else:
			heapq.heappush(heap, -z)
		if c[y]:
			c[y] -= 1
			n -= 1
		else:
			heapq.heappush(heap, -y)
	if len(heap) == 0:
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	print(ans(n, l, c))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	st = dict()
	for i in a:
		st[i] = st.get(i, 0) + 1
	nums = [total]
	ans = True
	while len(st) > 0 and len(nums) > 0:
		lt = nums.pop()
		if st.get(lt, 0) > 0:
			st[lt] = st.get(lt) - 1
			if st[lt] == 0:
				st.pop(lt)
			continue
		if lt == 1:
			ans = False
			break
		nums.append(lt // 2)
		nums.append((lt + 1) // 2)
	if len(st) > 0 or len(nums) > 0:
		ans = False
	print('YES' if ans else 'NO')


import math
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	o = sum(nums)
	nums_count = {x: 0 for x in nums}
	for item in nums:
		nums_count[item] += 1
	stack = [o]
	valid = [o]
	done = {o: 1}
	can = False
	if n == 1:
		can = True
	times = 0
	while times < n:
		if not stack:
			break
		tmp = stack
		stack = []
		for current in tmp:
			node1 = math.ceil(current / 2)
			node2 = current // 2
			if nums_count.get(node1):
				nums_count[node1] -= 1
			elif node1 > 1:
				stack.append(node1)
			if nums_count.get(node2):
				nums_count[node2] -= 1
			elif node2 > 1:
				stack.append(node2)
		if len(stack) > n:
			break
		times += 1
	if sum(nums_count.values()) == 0:
		can = True
	if can:
		print('YES')
	else:
		print('NO')


import sys
import heapq as hq

def _input_iter():
	for line in sys.stdin:
		for part in line.strip().split(' '):
			stripped = part.strip()
			if stripped:
				yield stripped
stream = _input_iter()

def read_int():
	return int(next(stream))

def read_str():
	return next(stream)

def run():
	n = read_int()
	a_h = []
	hq.heapify(a_h)
	for _ in range(n):
		hq.heappush(a_h, -read_int())
	h = []
	hq.heappush(h, sum(a_h))
	while len(a_h) > 0:
		if a_h[0] == h[0]:
			hq.heappop(a_h)
			hq.heappop(h)
		elif a_h[0] < h[0]:
			print('NO')
			return
		else:
			curr_elem = h[0]
			hq.heappop(h)
			hq.heappush(h, curr_elem // 2)
			hq.heappush(h, curr_elem // 2 + curr_elem % 2)
	print('YES')
test_cases = read_int()
for _ in range(test_cases):
	run()


import heapq

def main():
	length = int(input())
	for _ in range(length):
		no_piece = int(input())
		lst = list(map(int, input().split()))
		isDivisible(no_piece, lst)

def isDivisible(length, lst):
	if length != len(lst):
		print('NO')
		return
	sum_val = sum(lst)
	heap1 = [-sum_val]
	heap2 = []
	for val in lst:
		heapq.heappush(heap2, -val)
	while heap2:
		while -heap1[0] > -heap2[0]:
			top = heapq.heappop(heap1)
			if top % 2 == 0:
				heapq.heappush(heap1, top // 2)
				heapq.heappush(heap1, top // 2)
			else:
				heapq.heappush(heap1, top // 2)
				heapq.heappush(heap1, top // 2 + 1)
		if heap1[0] == heap2[0]:
			heapq.heappop(heap1)
			heapq.heappop(heap2)
		else:
			print('NO')
			return
	print('YES')
main()


import math
import heapq as h

def solve(A, B):
	w = sum(A)
	B.append(w * -1)
	A = [i * -1 for i in A]
	h.heapify(A)
	h.heapify(B)
	while A and B and (A[0] >= B[0]):
		if A[0] == B[0]:
			h.heappop(A)
			h.heappop(B)
		elif A[0] != B[0]:
			b = h.heappop(B)
			h.heappush(B, math.ceil(b / 2))
			h.heappush(B, math.floor(b / 2))
	if not A:
		print('YES')
	else:
		print('NO')
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().strip().split()))
	B = []
	solve(A, B)


from collections import defaultdict, deque
import math
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	temp = deque()
	d = defaultdict(lambda : 0)
	s = 0
	flag = 0
	ops = 0
	for x in range(n):
		d[a[x]] += 1
		s += a[x]
	temp.append(s)
	while len(temp) > 0:
		v = temp.popleft()
		if d[v] <= 0:
			if ops == n - 1:
				flag = 1
				break
			if math.floor(v / 2) <= 0:
				flag = 1
				break
			ops += 1
			temp.appendleft(math.floor(v / 2))
			temp.appendleft(math.ceil(v / 2))
		else:
			d[v] = d[v] - 1
	if flag == 1:
		print('NO')
	else:
		print('YES')
	t -= 1


import heapq
from math import ceil, floor

def resolve():
	npedacos = int(input())
	pedacos = [-int(x) for x in input().split(' ')]
	heapq.heapify(pedacos)
	tentativa = [sum(pedacos)]
	while len(pedacos) > 0:
		maior_tentativa = -heapq.heappop(tentativa)
		maior_atual = -pedacos[0]
		if maior_tentativa == maior_atual:
			heapq.heappop(pedacos)
		elif maior_tentativa > maior_atual:
			heapq.heappush(tentativa, -ceil(maior_tentativa / 2.0))
			heapq.heappush(tentativa, -floor(maior_tentativa / 2.0))
		else:
			print('NO')
			return
	print('YES')
ncasos = int(input())
for _ in range(ncasos):
	resolve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set()
	k = {}
	su = 0
	for i in a:
		if i in s:
			k[i] += 1
		else:
			k[i] = 1
			s.add(i)
		su += i
	vec = [su]
	p = 0
	i = 0
	flag = True
	while flag and i < len(vec) and (n >= 0):
		c = vec[i]
		if c in s and k[c] > 0:
			k[c] -= 1
			if k[c] == 0:
				p += 1
		else:
			if c == 1:
				flag = False
				break
			vec.append(int(c / 2))
			vec.append(round(c / 2 + 0.1))
			n -= 1
		i += 1
	if flag and p == len(s):
		print('YES')
	else:
		print('NO')


import heapq

def solve():
	_ = int(input())
	fin = list(map(int, input().strip().split()))
	fin = [-x for x in fin]
	heapq.heapify(fin)
	curr = [sum(fin)]
	while fin:
		while -curr[0] > -fin[0]:
			x = -heapq.heappop(curr)
			if x < 2:
				return False
			heapq.heappush(curr, -(x // 2))
			heapq.heappush(curr, -(x - x // 2))
		if -curr[0] != -fin[0]:
			return False
		heapq.heappop(fin)
		heapq.heappop(curr)
	return True
t = int(input())
for _ in range(t):
	res = 'NO'
	if solve():
		res = 'YES'
	print(res)


for _ in range(int(input())):
	length = int(input())
	l = list(map(int, input().split()))
	from collections import Counter
	freq = Counter(l)
	stack = []
	total = sum(l)
	stack.append(total)
	while len(stack):
		if stack[-1] in freq and freq[stack[-1]] > 0:
			freq[stack[-1]] -= 1
			stack.pop()
		else:
			temp = stack.pop()
			if temp == 1:
				break
			stack.append(temp // 2)
			stack.append((temp + 1) // 2)
	if len(stack):
		print('NO')
	else:
		print('YES')


import bisect
import math

def task10(w1):
	w1.sort()
	w2 = [sum(w1)]
	while len(w1) != 0 and len(w2) != 0:
		if w1[-1] > w2[-1]:
			return 'NO'
		elif w1[-1] == w2[-1]:
			w1.pop(-1)
			w2.pop(-1)
		else:
			item = w2.pop(-1)
			bisect.insort(w2, math.ceil(item / 2))
			bisect.insort(w2, math.floor(item / 2))
	return 'YES'
import heapq

def task10(w1):
	w1 = [-item for item in w1]
	w2 = [sum(w1)]
	heapq.heapify(w1)
	heapq.heapify(w2)
	while len(w1) != 0 and len(w2) != 0:
		if w1[0] < w2[0]:
			return 'NO'
		elif w1[0] == w2[0]:
			heapq.heappop(w1)
			heapq.heappop(w2)
		else:
			item = heapq.heappop(w2)
			heapq.heappush(w2, math.ceil(item / 2))
			heapq.heappush(w2, math.floor(item / 2))
	return 'YES'
result = []
t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split()
	arr = [int(arr[i]) for i in range(len(arr))]
	result.append(task10(arr))
for item in result:
	print(item)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	h = {}
	do = n - 1
	if l.count(1) == len(l):
		print('YES')
		continue
	if len(l) == 2 and abs(l[0] - l[1]) > 1:
		print('NO')
		continue
	for i in l:
		if i in h:
			h[i] += 1
		else:
			h[i] = 1
	arr = [s]
	ct = 0
	while ct < do and sum(h.values()) != 0:
		ll = len(arr)
		for i in range(len(arr)):
			if arr[i] in h and h[arr[i]] > 0:
				h[arr[i]] -= 1
			else:
				ct += 1
				arr.append(math.floor(arr[i] / 2))
				arr.append(math.ceil(arr[i] / 2))
		arr = arr[ll:]
	for i in range(len(arr)):
		if arr[i] in h and h[arr[i]] > 0:
			h[arr[i]] -= 1
	if sum(h.values()) == 0:
		print('YES')
	else:
		print('NO')


import math as m
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	s = sum(lst)
	a_dict = {}
	for i in lst:
		if i in a_dict:
			a_dict[i] += 1
		else:
			a_dict[i] = 1
	ans = [s]
	while ans:
		x = ans[0]
		if x == 0:
			break
		elif a_dict.get(ans[0], 'np') != 'np' and a_dict[ans[0]] != 0:
			a_dict[ans[0]] -= 1
			ans.pop(0)
		elif a_dict.get(ans[0], 'np') == 0:
			a_dict.pop(ans[0])
		else:
			r = ans[0]
			ans.pop(0)
			ans.insert(0, m.floor(r / 2))
			ans.insert(1, m.ceil(r / 2))
	q = 0
	fa = 'YES'
	for k in a_dict:
		q += a_dict[k]
		if q > 0:
			fa = 'NO'
			break
	print(fa)


import math
from heapq import heapify, heappush, heappop

def solution(k, cakes):
	current = [-sum(cakes)]
	numbers = [-i for i in cakes]
	heapify(numbers)
	i = 1
	while i < k:
		(c, n) = (-1 * heappop(current), -1 * heappop(numbers))
		if c > n:
			(a, b) = (-1 * math.floor(c / 2), -1 * math.ceil(c / 2))
			heappush(current, a)
			heappush(current, b)
			heappush(numbers, -1 * n)
			i += 1
		elif c == n:
			continue
		else:
			return 'NO'
	while current and numbers and (current[0] == numbers[0]):
		heappop(current)
		heappop(numbers)
	if len(numbers) == 0:
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	n = int(input())
	cakes = list(map(int, input().split()))
	print(solution(n, cakes))


from collections import Counter
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	sum1 = sum(a)
	x = Counter(a)
	q = []
	q.append(sum1)
	flag = 0
	while q:
		if max(x) > max(q):
			flag = 1
			break
		if 1 in q and 1 not in x:
			flag = 1
			break
		x1 = q.pop()
		if x1 in x:
			x[x1] -= 1
			if x[x1] == 0:
				x.pop(x1)
		elif x1 % 2 == 0:
			q.append(x1 // 2)
			q.append(x1 // 2)
		else:
			q.append(x1 // 2)
			q.append(x1 // 2 + 1)
	if x or flag == 1:
		print('NO')
	else:
		print('YES')


import sys, math, queue, bisect
input = sys.stdin.readline

def f(n):
	nums_length = len(nums)
	q = queue.PriorityQueue()
	q.put([-n, 1])
	while q.qsize() != 0:
		(cur_node, cur_count) = q.get()
		while q.qsize() != 0:
			(tmp_node, tmp_count) = q.get()
			if tmp_node == cur_node:
				cur_count += tmp_count
			else:
				q.put([tmp_node, tmp_count])
				break
		cur_node *= -1
		if cur_node < nums[nums_length - 1]:
			return False
		length_to_remove = min(nums_length - bisect.bisect_right(nums, cur_node - 1), cur_count)
		nums_length -= length_to_remove
		cur_count -= length_to_remove
		if nums_length <= 0:
			return True
		if cur_node >= 2 and cur_count > 0:
			if cur_node % 2 == 0:
				q.put([-cur_node // 2, cur_count * 2])
			else:
				q.put([-math.ceil(cur_node / 2), cur_count])
				q.put([-math.floor(cur_node / 2), cur_count])
	return False
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	if f(sum(nums)):
		print('YES')
	else:
		print('NO')


t = int(input())

class Node:

	def __init__(self, val, r=None, l=None):
		self.value = val
		self.right = r
		self.left = l
for _ in range(t):
	nuuu = int(input())
	nums = [int(x) for x in input().split()]
	mp = {}
	for num in nums:
		if num not in mp:
			mp[num] = 1
		else:
			mp[num] += 1
	tot = sum(nums)
	from collections import deque
	s = Node(tot)
	q = deque()
	q.append(s)
	d = False
	moves = 0
	while len(q):
		n = q.popleft()
		if moves > nuuu - 1:
			d = True
			break
		if n.value in mp and mp[n.value] > 0:
			mp[n.value] -= 1
		elif n.value == 1:
			d = True
			break
		else:
			n.left = Node(n.value // 2)
			n.right = Node((n.value + 1) // 2)
			q.append(n.right)
			q.append(n.left)
			moves += 1
	if d:
		print('NO')
	else:
		print('YES')