You are given an array A = [A_{1}, A_{2}, \ldots, A_{N}].

Is it possible to partition A into two non-empty [subsequences] S_{1} and S_{2} such that sum(S_{1}) \times sum(S_{2}) is odd?

Here, sum(S_{1}) denotes the sum of elements in S_{1}, and sum(S_{2}) is defined similarly.

Note: S_{1} and S_{2} must *partition* A, that is:
S_{1} and S_{2} must be non-empty
Every element of A must be in either S_{1} or S_{2}
S_{1} and S_{2} must be disjoint (in terms of which indices their subsequences represent)

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

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

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

For each test case, print on a new line the answer: YES if the array can be partitioned into two subsequences satisfying the condition, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, YES, yes, YEs, and yEs will all be treated as equivalent.

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

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

----- Sample Input 1 ------ 
4
4
1 1 2 2
6
1 2 4 6 8 10
2
3 5
3
1 3 5
----- Sample Output 1 ------ 
YES
NO
YES
NO
----- explanation 1 ------ 
Test case $1$: We have $A = [\underline{1}, 1, \underline{2}, 2]$. Let $S_{1}$ be the underlined elements and $S_{2}$ be the other ones. $sum(S_{1}) \times sum(S_{2}) = 3\times 3 = 9$.

Test case $2$: It can be proved that no partition of $A$ into $S_{1}, S_{2}$ satisfies the condition.

Test case $4$: Choose $S_{1} = \{3\}, S_{2} = \{5\}$.

Test case $4$: It can be proved that no partition of $A$ into $S_{1}, S_{2}$ satisfies the condition.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	o = 0
	for i in range(len(l)):
		if l[i] % 2 != 0:
			o += 1
	if o % 2 == 0 and o > 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	odd = 0
	for k in a:
		if k % 2 == 1:
			odd += 1
	if odd == 0:
		print('NO')
	elif odd % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = c = 0
	for i in a:
		if i % 2 == 1:
			c += 1
	if c % 2 == 1 or c == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	x = int(input())
	list1 = list(map(int, input().split()))
	list2 = []
	indexi = 0
	for i in range(x):
		if list1[i] % 2 == 1:
			list2.append(list1[i])
			indexi = list1.index(list1[i])
			break
	list1.pop(indexi)
	if len(list2) > 0:
		if sum(list1) * sum(list2) % 2 == 1:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	x = int(input())
	list1 = list(map(int, input().split()))
	even = 0
	odd = 0
	for i in range(x):
		if list1[i] % 2 == 0:
			even += 1
		else:
			odd += 1
	if x == even:
		print('NO')
	elif sum(list1) % 2 == 0 and odd >= 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	c = 0
	for i in L:
		if i % 2 != 0:
			c += 1
	if c % 2 == 0 and c != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	c = 0
	arr = list(map(int, input().split()))
	for i in range(0, n):
		if arr[i] % 2 != 0:
			c = c + 1
	if c % 2 == 0 and c > 0:
		print('YES')
	else:
		print('NO')


a = int(input())
for i in range(0, a):
	y = int(input())
	b = list(map(int, input().split()))
	h = []
	o = []
	for i in b:
		if i % 2 == 0:
			h.append(i)
		else:
			o.append(i)
	if len(o) % 2 != 0 or len(o) == 0:
		print('NO')
	else:
		print('YES')


T = int(input())
if 1 <= T <= 10 ** 5:
	for i in range(T):
		N = int(input())
		A = list((int(x) for x in input().split()))
		odd_count = 0
		for i in A:
			if i % 2 == 1:
				odd_count = odd_count + 1
		if odd_count % 2 == 1 or odd_count == 0:
			print('NO')
		else:
			print('YES')


n = int(input())
for i in range(n):
	l = int(input())
	lis = list(map(int, input().split()))
	o_count = 0
	for a in range(l):
		if lis[a] % 2 != 0:
			o_count += 1
	print('YES' if o_count != 0 and o_count % 2 == 0 else 'NO')


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	count = 0
	for i in L:
		if i % 2 == 1:
			count += 1
	if count == 0 or count % 2 == 1:
		print('NO')
	else:
		print('YES')


tb = int(input())
for i in range(tb):
	n = int(input())
	ll = list(map(int, input().split()))
	total = sum(ll)
	(lsum, rsum) = (0, 0)
	flag = True
	for i in range(len(ll)):
		lsum += ll[i]
		rsum = total - lsum
		if lsum * rsum % 2:
			print('YES')
			flag = False
			break
	if flag:
		print('NO')


for _ in range(int(input())):
	lent = int(input())
	arr1 = [int(x) for x in input().split()]
	odds = 0
	if lent == 1:
		print('NO')
		continue
	for y in arr1:
		if y % 2 == 1:
			odds += 1
	if odds != 0 and odds % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	odd_count = 0
	for i in range(N):
		if A[i] % 2 != 0:
			odd_count += 1
	if odd_count % 2 == 0 and odd_count > 0:
		print('YES')
	elif odd_count == 0:
		print('NO')
	else:
		print('NO')


cases = int(input())
for i in range(cases):
	n = int(input())
	a = list(map(int, input().split()))
	o = []
	e = []
	for j in a:
		if j % 2 != 0:
			o.append(j)
		else:
			e.append(j)
	if len(o) % 2 == 0 and len(o) > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for j in range(0, n):
		if a[j] % 2 != 0:
			c = c + 1
	if c % 2 == 0 and c > 0:
		print('YES')
	else:
		print('NO')


for j in range(int(input())):
	length = int(input())
	my_list = list(map(int, input().split()))
	(odd_count, even_count) = (0, 0)
	for i in my_list:
		if i % 2 != 0:
			odd_count += 1
	if odd_count % 2 == 0 and odd_count > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	dic = dict()
	dic['odd'] = 0
	for i in a:
		if i % 2 != 0:
			dic['odd'] += 1
	if dic['odd'] % 2 == 0 and dic['odd'] != 0:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	even = []
	odd = []
	N = int(input())
	ls = list(map(int, input().split()))
	counter = 0
	for i in range(N):
		if ls[i] % 2 != 0:
			counter += 1
	if sum(ls) % 2 == 0 and N >= 2 and (counter != 0):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n < 2:
		print('NO')
	else:
		o = 0
		for i in range(n):
			if a[i] % 2 != 0:
				o += 1
		if sum(a) % 2 == 0 and o != 0:
			print('YES')
		else:
			print('NO')


try:
	t = int(input())
	for r in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		even = 0
		odd = 0
		for i in range(n):
			if a[i] % 2:
				even += 1
		if even == 0 or even % 2:
			print('NO')
		else:
			print('YES')
except:
	pass


for T in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	numOdd = 0
	for i in a:
		if i % 2 != 0:
			numOdd += 1
	if numOdd == 0:
		print('NO')
	elif numOdd % 2 == 0:
		print('YES')
	else:
		print('NO')


tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = map(int, input().split())
	oddcount = 0
	for k in arr:
		if k & 1:
			oddcount += 1
	if oddcount & 1 == 1 or oddcount == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	le = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		if i % 2 != 0:
			s += 1
	if s % 2 == 0 and s > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	for j in l:
		if j % 2 != 0:
			cnt += 1
	if cnt % 2 == 0 and cnt != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	x = int(input())
	l = list(map(int, input().split()))
	odd = 0
	even = 0
	for x in l:
		if x % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
	if odd % 2 == 0 and odd > 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	A = int(input())
	L = list(map(int, input().split()))
	Odds = 0
	Evens = 0
	for _ in range(len(L)):
		if L[_] % 2 == 0:
			Evens += 1
		else:
			Odds += 1
	if Odds % 2 == 0 and Odds > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	(count_odd, count_even) = (0, 0)
	for i in a:
		if i % 2 == 0:
			count_even += 1
		else:
			count_odd += 1
	if count_odd % 2 == 0 and count_odd > 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd_nos = list(filter(lambda x: x % 2 != 0, l))
	if len(odd_nos) % 2 == 0 and len(odd_nos) != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split(' ')
	l_odd = []
	for j in range(n):
		if int(arr[j]) % 2 != 0:
			l_odd.append(arr[j])
	if len(l_odd) % 2 == 0 and len(l_odd) != 0:
		print('YES')
	else:
		print('NO')


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


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s1 = []
	s2 = []
	counto = 0
	for i in a:
		if i % 2 == 0:
			s1.append(i)
		else:
			s2.append(i)
			counto += 1
	if counto % 2 == 0 and counto > 0:
		print('YES')
	else:
		print('NO')


import numpy as np
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	s1 = 0
	for i in range(0, n):
		if a[i] % 2 != 0:
			s1 += 1
	if s1 % 2 == 0 and s1 != 0:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	count = 0
	for i in range(x):
		if y[i] % 2 == 1:
			count = count + 1
	if count == 0 or count % 2 == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	arr = [int(j) for j in input().split()]
	odd = 0
	for j in arr:
		if j % 2 != 0:
			odd += j
	if odd % 2 == 0 and odd > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	x = int(input())
	sum = 0
	n = list(map(int, input().split()))
	for i in n:
		if i % 2 != 0:
			sum = sum + i
	if sum % 2 == 0 and sum > 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	c = 0
	for z in range(x):
		if l[z] % 2 != 0:
			c = c + 1
	if c % 2 != 0 or c == 0:
		print('NO')
	else:
		print('YES')