Let F(S) denote the number of distinct elements in the array S. For example, F([1, 2, 3, 2]) = 3, F([1, 2]) = 2.

You are given an array A containing N integers. Find if it is possible to divide the elements of the array A into two arrays B and C such that :
Every element of the array A belongs either to array B or to array C.
F(B) = F(C).

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N — the length of the array A.
- The next line contains N space-separated integer A_{1}, A_{2}, \dots, A_{N}, denoting the elements of the array A.

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

For each test case, print YES if it is possible to divide the elements of the array A into two arrays B, C satisfying all the conditions and NO otherwise.

You may print each character of the 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}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
1 2
3
1 2 3
4
3 1 1 2

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: One possible division is $B = [1], C = [2]$. Here $F(B) = F(C) = 1.$

Test case $2$: There is no way to distribute the elements of the array $A = [1, 2, 3]$ satisfying all the conditions.

Test case $3$: One possible division is $B = [3, 1], C = [1, 2]$. Here $F(B) = F(C) = 2.$

Difficulty: EASY
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 0:
		print('YES')
	elif len(set(a)) == n:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	freq = {}
	for i in arr:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	distinct = 0
	for i in freq:
		if freq[i] == 1:
			distinct += 1
	if distinct % 2 == 1 and distinct == n:
		print('NO')
	else:
		print('YES')


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = len(a)
	b = set(a)
	d = len(b)
	if d % 2 == 0 or d < n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	new_n = len(b)
	if new_n % 2 == 0 or new_n < n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 'YES'
	if n % 2 and len(set(a)) == n:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	n_list = list(map(int, input().split()))
	print('YES' if len(n_list) % 2 == 0 or len(set(n_list)) < n else 'NO')


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	x = len(set(l))
	if x % 2 == 0 or x < len(l):
		print('YES')
	else:
		print('NO')


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	flag = 1
	s = set(arr)
	if n % 2 != 0:
		if len(s) == len(arr):
			flag = 0
	if flag == 0:
		print('NO')
	else:
		print('YES')


from collections import Counter
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = Counter(a)
	c = [x for (x, y) in b.items() if y == 1]
	if len(c) % 2 == 0 or len(c) < n:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(n) for n in input().split()]
	l = len(list(set(a)))
	s = ''
	if l == n and l % 2 != 0:
		s = 'NO'
	elif l % 2 == 0 and l == n:
		s = 'YES'
	else:
		s = 'YES'
	print(s)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	if a == len(list(set(l))):
		if a % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


r = int(input())
while r > 0:
	r = r - 1
	n = int(input())
	a = map(int, input().split())
	d = len(set(a))
	if d % 2 == 0 or d < n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	from collections import Counter
	x = Counter(a)
	flag = 0
	if len(a) % 2 == 0:
		print('YES')
	else:
		for i in x.values():
			if i > 1:
				print('yes')
				flag = 1
				break
		if flag == 0:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a_set = list(set(a))
	if len(a_set) == len(a):
		if len(a_set) % 2 == 1:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dict = {}
	flag = False
	for i in a:
		if i in dict:
			flag = True
			dict[i] = dict[i] + 1
		else:
			dict[i] = 1
	if len(dict) % 2 == 0:
		print('YES')
	else:
		if flag:
			print('YES')
			continue
		print('NO')


for _ in range(int(input())):
	n = int(input())
	list1 = list(input().split())
	s = set(list1)
	if len(list1) == len(s) and n % 2 == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	len_set = len(set(ar))
	if n % 2 != 0 and n == len_set:
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	a = list(set(map(int, input().split())))
	if len(a) % 2 == 0 or len(a) < n:
		print('YES')
	else:
		print('NO')


T = int(input())
arr = []
arr2 = []
while T:
	T -= 1
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	length = len(set(arr))
	if length % 2 == 0 or length < n:
		print('YES')
	else:
		print('NO')


t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(set(arr)) == n:
		if n % 2 != 0:
			print('NO')
			continue
	print('YES')


from collections import Counter
a = int(input())
for i in range(a):
	x = int(input())
	l = list(map(int, input().split(' ')))
	l1 = Counter(l)
	w = list(l1.keys())
	x = list(l1.values())
	y = len(w)
	z = sum(x)
	if y == z and y % 2 != 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = int(input())
	list_a = list(map(int, input().split()))
	set_a = set(list_a)
	if len(set_a) == len(list_a) and len(set_a) % 2 != 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = set(l)
	set_len = len(a)
	if set_len == n and n % 2 != 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	a = int(input())
	l1 = list(map(int, input().split()))
	l2 = set(l1)
	l3 = len(l2)
	key = 0
	if a % 2 != 0:
		if a - l3 == 0:
			key = 1
	if key == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sl = set(l)
	nl = len(sl)
	if nl % 2 == 1 and nl == n:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) < n or n & 1 == 0:
		print('YES')
	else:
		print('NO')


from collections import Counter as C
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) < n or n & 1 == 0:
		print('YES')
	else:
		print('NO')


from collections import Counter
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	c = Counter(A)
	l = 0
	for j in c.values():
		if j == 1:
			l += 1
	if l % 2 != 0 and l == N:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()][:N]
	if len(set(A)) == N and N % 2 != 0:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	n = int(input())
	li = list(map(int, input().split()))
	if n == 2:
		print('YES')
	elif len(set(li)) < n:
		print('YES')
	elif n % 2 == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = list(set(l))
	if len(l) % 2 == 1 and len(l) == len(s):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(num) for num in input().split(' ', n - 1)]
	k = set(a)
	l = len(k)
	if n % 2 != 0 and n == l:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
ans = []
for _ in range(inp()):
	N = inp()
	l = len(set(inlt()))
	ans.append('NO' if l % 2 and N == l else 'YES')
outplt(ans)


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	d = {}
	for a in A:
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
	ans.append('NO' if len(d.keys()) % 2 and N == len(d) else 'YES')
outplt(ans)


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split(' ')]
	if n % 2 != 0 and len(set(l)) == n:
		print('NO')
	else:
		print('YES')


import collections
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	b = dict(collections.Counter(a))
	for (keys, values) in b.items():
		l.append(values)
	if n % 2 != 0 and len(l) == n:
		print('NO')
	else:
		print('YES')


import collections
t = int(input())
for i in range(t):
	N = int(input())
	Arr = list(map(int, input().split(' ')))
	frequency = collections.Counter(Arr)
	if N % 2 != 0 and len(frequency) == N:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if len(s) & 1 == 0 or len(s) < n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = list(set(l))
	r = len(x)
	if r % 2 == 1 and n == r:
		print('NO')
	else:
		print('YES')


a = int(input())
for i in range(a):
	k = int(input())
	l = list(map(int, input().split()))
	m = len(set(l))
	if m % 2 == 0 or m < k:
		print('YES')
	else:
		print('NO')


def distinct(n, arr):
	d = len(set(arr))
	if d % 2 == 0 or d < n:
		return 'YES'
	else:
		return 'NO'
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(distinct(n, arr))


def find_answer():
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) % 2 == 0:
		return 'YES'
	if len(set(a)) != len(a):
		return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	print(find_answer())


t = int(input())
for x in range(t):
	n1 = int(input())
	arr = list(map(int, input().split()))
	ar = [*set(arr)]
	n2 = len(ar)
	if n1 == n2:
		if n1 % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif n1 > n2:
		print('YES')


from collections import Counter

def F(S):
	return len(Counter(S).keys())
T = int(input())
for i in range(T):
	x = int(input())
	l = [int(k) for k in input().split()]
	if F(l) % 2 == 0 or x > F(l):
		print('YES')
	else:
		print('NO')