Dazzler has an interesting task for you.

You will be given an array A of N positive integers such that:
N is always even.
Exactly \frac{N}{2} elements in the array are even and \frac{N}{2} elements are odd.

In one operation, you should do the following steps:
Choose two different indices i and j  (1 ≤ i,j ≤ N).
Set A_{i} := A_{i} + 1.
Set A_{j} := A_{j} - 1.

You need to apply some finite (possibly zero) number of operations on the array such that:
The [parity] of the final element at each index is same as the parity of the initial element at that index. For example, if the i^{th} element in the initial array is even, then, the i^{th} element in the final array must be even as well.
All the \frac{N}{2} odd elements in the final array are equal.
All the \frac{N}{2} even elements in the final array are equal.

Print YES if it is possible to meet all the above conditions after doing some finite (possibly zero) number of operations. Otherwise, print NO.

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

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains N, number of elements in the array A. Note that, N is even.
- Second line of each test case contains N space-separated positive integers, the elements of the array.

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

For each test case, output in a single line, YES if it is possible to meet all the given conditions after doing some finite (possibly zero) number of operations. Otherwise, print NO.

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

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

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A[i] ≤ 10^{9}$
$N \% 2 = 0$ 
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
1 1 2 4
4
1 2 5 6
2
1 2
4
1 2 3 4

----- Sample Output 1 ------ 
NO
YES
YES
YES
----- explanation 1 ------ 
Test case $1$: It is not possible to satisfy all the given conditions using any number of operations.

Test case $2$: One of the possible sequence of operations is listed below:
- In the first operation, choose $i=2$ and $j=4$. Thus, $A_{2} = 2+1=3$ and $A_{4} = 6-1=5$. The array will become $[1,3,5,5]$.
- In the second operation, choose $i=2$ and $j=4$. Thus, $A_{2} = 3+1=4$ and $A_{4} = 5-1=4$. The array will become $[1,4,5,4]$.
- In the third operation, choose $i=1$ and $j=3$. Thus, $A_{1} = 1+1=2$ and $A_{3} = 5-1=4$. The array will become $[2,4,4,4]$.
- In the fourth operation, choose $i=1$ and $j=3$. Thus, $A_{1} = 2+1=3$ and $A_{3} = 4-1=3$. The array will become $[3,4,3,4]$.

Here, all the odd elements are equal and all the even elements are equal. Also, the parity at each index is preserved.

Test case $3$: The array $[1,2]$ satisfies all the conditions. Thus, $0$ operations are needed.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	x = N // 2
	s = sum(A)
	if s % x != 0:
		print('NO')
	elif s // x % 2 == 0:
		print('NO')
	else:
		print('YES')


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	min_odd = float('inf')
	max_even = 0
	min_even = float('inf')
	d = defaultdict(lambda : 0)
	b = defaultdict(lambda : 0)
	for i in A:
		if i % 2 == 1:
			if i < min_odd:
				min_odd = i
		if i % 2 == 0:
			if i > max_even:
				max_even = i
			if i < min_even:
				min_even = i
	sm1 = 0
	sm2 = 0
	for i in A:
		if i % 2 == 1:
			sm1 += i - min_odd
		if i % 2 == 0:
			sm2 += max_even - i
	x = abs(sm1 - sm2) % N / 2
	if x == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = n // 2
	s = sum(a)
	if s % x != 0:
		print('NO')
	elif s // x % 2 == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	N = int(input())
	A = [int(k) for k in input().split()]
	a = sum(A)
	if (a - N // 2) % N:
		print('NO')
	else:
		print('YES')


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def calc(s):
	ans = 0
	for ele in s:
		ans += ord(ele) - 96
	return ans

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	x = sum(l) * 2
	if x % n == 0 and x // n % 2 == 1:
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	print(solve())


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(ele) for ele in input().split()]
	arr_sum = sum(arr)
	n = len(arr)
	if arr_sum % (n // 2) == 0 and arr_sum // (n // 2) % 2 != 0:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(e, o) = ([], [])
	for x in arr:
		if x % 2 == 0:
			e.append(x)
		else:
			o.append(x)
	omax = max(o)
	(ed, od) = (0, 0)
	for i in range(n // 2):
		ed += e[i] - 2
		od += omax - o[i]
	ed -= od
	if ed % n == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	n = n // 2
	k = s / n
	if k != int(k):
		print('NO')
	elif k % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = sum(list(map(int, input().split())))
	print('YES') if l / (n // 2) % 2 == 1 else print('NO')


def solve(arr):
	return 'YES' if 2 * sum(arr) % n == 0 and 2 * sum(arr) / n % 2 == 1 else 'NO'
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(arr))


for i in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	s = sum(nums) * 2
	if s % n == 0 and s // n % 2 == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	s = sum(arr)
	if s / (n // 2) % 2 == 1:
		print('YES')
	else:
		print('NO')


tsc = int(input())
for i in range(tsc):
	N = int(input())
	s = 0
	arr = [int(k) for k in input().split()]
	for i in arr:
		s += i
	if 2 * s % N != 0:
		print('NO')
	else:
		print('NO') if int(2 * s / N) % 2 == 0 else print('YES')


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	sum_lst = sum(lst)
	if sum_lst // (n // 2) % 2 == 1 and sum_lst % (n // 2) == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	if (sum(a) - N // 2) % N:
		print('NO')
	else:
		print('YES')


from collections import *

def solve(A):
	total = sum(A)
	N = len(A)
	if N % 2:
		return 'NO'
	return 'YES' if (total - N // 2) % N == 0 else 'NO'
for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve(A))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	if (s - n // 2) % n == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	s1 = sum(a)
	s2 = sum(a) * 2
	s = sum(a) * 2 // n
	i = 1
	if s2 % n == 0 and s % 2 != 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	r = n // 2
	if s % r:
		print('NO')
	elif s // r % 2:
		print('YES')
	else:
		print('NO')


from math import ceil
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if (s - n / 2) % n == 0:
		print('YES')
	else:
		print('NO')


import math
from statistics import mean
tc = int(input())
while tc > 0:
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if (s - n / 2) % n == 0:
		print('YES')
	else:
		print('NO')
	tc -= 1


for _ in range(int(input())):
	n = int(input())
	nums = map(int, input().split())
	s = sum(nums)
	x = s + n // 2
	y = s - n // 2
	if x % n == 0 and y % n == 0:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	s -= n // 2
	if s / n == int(s / n):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	s = sum(nums)
	if 2 * s % n == 0 and 2 * s // n % 2 != 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	a = sum(A)
	b = N / 2
	if a / b % 2 == 1:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for I in arr:
		if I & 1:
			odd.append(I)
		else:
			even.append(I)
	o = max(odd)
	e = min(even)
	(co, ce) = (0, 0)
	for i in odd:
		co += o - i
	for i in even:
		ce += i - e
	if ce == co:
		print('YES')
	elif ce > co and (not (ce - co) % n):
		print('YES')
	elif ce < co and (not (co - ce) % n):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	f = 0
	s = sum(arr)
	for j in range(1, n, 2):
		so = n // 2 * j
		se = s - so
		if se % 2 != 0:
			continue
		if se % n // 2 != 0:
			continue
		e = se // (n // 2)
		if e % 2 == 0:
			f = 1
			break
	if f == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % n == n // 2:
		print('YES')
	else:
		print('NO')


import sys
MYPC = False
if MYPC:
	sys.stdin = open('in.txt', 'r')
	sys.stdout = open('out.txt', 'w')
input = sys.stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		a = [int(x) for x in input().split()]
		s = sum(a)
		odd_sum = sum([x for x in a if x & 1])
		even_sum = s - odd_sum
		n = n // 2
		if s % n != 0:
			print('NO')
			continue
		s = s // n
		if s % 2 == 0:
			print('NO')
			continue

		def check(i):
			(inc, dec) = (0, 0)
			v = [i, s - i]
			inc = sum([v[x % 2] - x for x in a if v[x % 2] > x])
			dec = sum([x - v[x % 2] for x in a if v[x % 2] < x])
			return inc == dec
		can = any((check(i) for i in range(1, -~s, 2)))
		print('YES' if can else 'NO')
main()


from math import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 2 * sum(a) % n == 0 and 2 * sum(a) // n % 2 != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
a = []
for i in range(2 * t):
	a += [list(map(int, input().split()))]

def f(x):
	n = len(x)
	s = sum(x)
	if s % (n // 2) == 0 and s // (n // 2) % 2 == 1:
		return 'YES'
	else:
		return 'NO'
for i in range(t):
	print(f(a[2 * i + 1]))


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

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

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		arr = lis()
		s = sum(arr)
		if s % (n // 2) != 0:
			print('NO')
			continue
		p = s // (n // 2)
		if p & 1:
			print('YES')
		else:
			print('NO')
main()


T = int(input())
while T > 0:
	N = int(input())
	A = list(map(int, input().split()))
	S = sum(A)
	y = (S - N // 2) / N
	if y.is_integer():
		print('YES')
	else:
		print('NO')
	T -= 1


t = int(input())
for _ in range(t):
	x = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if (s - x / 2) % x == 0:
		print('YES')
	else:
		print('NO')


import sys, os
from sys import stdin, stdout
io_path = 'E:\\Personal\\competitve-programming\\IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

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

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

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	n = int(input())
	elements = get_ints_list()
	odd_sum = 0
	even_sum = 0
	for i in elements:
		if i % 2 == 0:
			even_sum += i
		else:
			odd_sum += i
	sum = even_sum + odd_sum
	ans = False
	if sum % (n // 2) == 0:
		if sum // (n // 2) % 2 != 0:
			ans = True
	if ans:
		print('YES')
	else:
		print('NO')
	test_cases -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if sum(A) * 2 % N == 0 and sum(A) * 2 // N % 2:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	l = list((int(x) for x in input().split()))
	sm = sum(l)
	if sm * 2 % n == 0:
		if sm * 2 // n % 2 != 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for test in range(t):
	n = int(input())
	lks = list(map(int, input().split()))
	s = sum(lks)
	ans = 'NO'
	if (s - n // 2) % n == 0:
		ans = 'YES'
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s1 = 0
	s2 = 0
	s = 0
	s = s + (1 & 0)
	x = n // 2
	for i in range(n):
		s = s + arr[i]
	val = s - (x - 1)
	s = s + (1 & 0)
	x2 = x * 2
	if (val - 1) % x2 == 0:
		print('YES')
	else:
		print('NO')


a = int(input())
for w in range(a):
	n = int(input())
	L = [int(s) for s in input().split()]
	add = sum(L)
	if add % (n / 2) == 0:
		ans = add / (n / 2)
		if ans % 2 == 0:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	sin = sum(nums) * 2
	if sin // N % 2 == 1 and sin % N == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = [int(j) for j in input().split()]
	print('YES' if sum(l) * 2 % n == 0 and sum(l) * 2 // n % 2 == 1 else 'NO')


tr = int(input())
for _ in range(tr):
	k = int(input())
	a = map(int, input().split())
	l = sum(a) * 2
	if l % k == 0 and l // k % 2 == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	number = int(input())
	last = list(map(int, input().split()))
	temprary = sum(last) * 2
	if temprary % number == 0 and temprary // number % 2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	sum1 = sum(a)
	p = n // 2
	sum1 = sum1 - p
	x = sum1 // p
	if x % 2 == 0 and sum1 % p == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum_a = sum(a)
	curr = sum_a + 1 - n // 2
	if (curr - 1) % n == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = int(input())
	no = list(map(int, input().split()))
	b = sum(no) * 2
	if b % a == 0 and b // a % 2 == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	N = int(input())
	num = list(map(int, input().split()))
	ss = sum(num) * 2
	if ss % N == 0 and ss // N % 2 == 1:
		print('YES')
	else:
		print('NO')