You are given an array A of length 2\cdot N.

You also have an empty array B. You are asked to do the following operation exactly N times. 

Choose two distinct indices x and y (1≤ x,y ≤ |A|);
Append (A_{x} - A_{y}) to the end of array B;
Delete the x^{th} and y^{th} elements from A and concatenate remaining elements without changing the order.

Find whether there exists a set of operations to get array B such that B_{i} \neq B_{(i+1)} (1 ≤ i < N).

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

- The first line of input contains 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 second line of each test case contains 2\cdot N space-separated integers A_{1},A_{2},\ldots,A_{2\cdot N} representing the array A.

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

For each test case, print on a new line the answer: YES if it is possible to obtain valid B, and NO otherwise.

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

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

$1 ≤ T ≤ 10^{3}$
$2 ≤ N ≤ 10^{3}$
$1 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $5 \cdot 10^{3}$.

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

----- Sample Output 1 ------ 
NO
YES
YES
----- explanation 1 ------ 
Test case $1$: No matter how we perform the operations, $B=[0,0]$.

Test case $2$: 
- In first operation, we can take $x=2$ and $y=3$. Now we append $A_{x}-A_{y}=1-2=-1$ at the back of $B$, and delete $A_{2}$ and $A_{3}$ from $A$. Now $A=[1,2,3,3]$.
- In second operation, we can take $x=2$ and $y=1$; append $A_{x} - A_{y} = 2-1 = 1$ at the back of $B$ and delete $A_{2}$ and $A_{1}$. Thus, $A = [3, 3]$ and $B = [-1, 1]$.
- In the third operation, we take $x=1$ and $y=2$; append $A_{x} - A_{y} = 3-3 = 0$ at the back of $B$ and delete $A_{1}$ and $A_{2}$. Thus, $A = []$ and $B = [-1, 1,0]$.

Thus, finally $B=[-1,1,0]$. There are no two consecutive elements in $B$ that are equal.

Test case $3$: 
- In first operation, we can take $x=2$ and $y=3$. Now we append $A_{x}-A_{y}=1-2=-1$ at the back of $B$, and delete $A_{2}$ and $A_{3}$ from $A$. Now $A=[1,2]$.
- In second operation, we can take $x=2$ and $y=1$; append $A_{x} - A_{y} = 2-1 = 1$ at the back of $B$ and delete $A_{2}$ and $A_{1}$. Thus, $A = []$ and $B = [-1, 1]$.

Thus, finally $B=[-1,1]$. There are no two consecutive elements in $B$ that are equal.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	mx = max((l.count(x) for x in l))
	print('YES' if mx - n <= (n + 1) // 2 else 'NO')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	d = defaultdict(lambda : 0)
	m = 0
	for i in A:
		d[i] += 1
		if d[i] > m:
			m = d[i]
	if (m - (2 * n - m)) // 2 > 2 * n - m + 1:
		print('NO')
	else:
		print('YES')


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	swap = True
	for i in c:
		if c[i] > 2 * n - n // 2:
			swap = False
	if swap == False:
		print('NO')
	else:
		print('YES')


def solve(n, arr):
	temp = {}
	maximum = 0
	for i in arr:
		if i in temp:
			temp[i] += 1
			maximum = max(maximum, temp[i])
		else:
			temp[i] = 1
			maximum = max(maximum, temp[i])
	if maximum - n <= n // 2 + (n & 1):
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	print(solve(int(input()), list(map(int, input().split()))))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	lastDistinct = n
	a.sort()
	for i in range(0, n):
		if a[i] == a[2 * n - i - 1]:
			lastDistinct = i
			break
	if n - lastDistinct > lastDistinct + 1:
		print('NO')
	else:
		print('YES')


import collections
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	most_e = max(collections.Counter(A).values())
	others = len(A) - most_e
	pairs = min(others, most_e)
	if most_e > pairs:
		max_nb_op = 2 * pairs + 1
		if max_nb_op >= N:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		d.setdefault(i, 0)
		d[i] += 1
	k = max(d.values())
	if k - n <= (n + 1) // 2:
		print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	n *= 2
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	m = -1
	for i in d:
		if d[i] > m:
			m = d[i]
	m -= n - m + (n - m + 1) * 2
	if m > 0:
		print('NO')
	else:
		print('YES')


import statistics
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = statistics.mode(l)
	count = l.count(m)
	r = 2 * n - count
	if count // 3 <= r:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	array = [int(i) for i in input().split()]
	d = {}
	for i in array:
		d.setdefault(i, 0)
		d[i] += 1
	count = max(d.values())
	if count - n <= (n + 1) // 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		d[i] = d.get(i, 0) + 1
	m = max(d.values())
	if m - n <= (n + 1) // 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for T in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = [0 for i in range(n)]
	for i in range(2 * n):
		count[a[i] - 1] += 1
	if max(count) > 2 * n - n // 2:
		print('NO')
	else:
		print('YES')


from heapq import heapify, heappush, heappop
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	h = {}
	for i in l:
		h[i] = 1 + h.get(i, 0)
	chk = False
	threshold = n + (n + 3) // 2
	for i in h.values():
		if i >= threshold:
			chk = True
			break
	if chk:
		print('NO')
	else:
		print('YES')


from collections import Counter
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	if len(set(l)) == 1:
		print('NO')
	else:
		c = Counter(l)
		v = c.values()
		cutoff = a + (a + 3) // 2
		if max(v) < cutoff:
			print('YES')
		else:
			print('NO')


from collections import Counter
for tea in range(int(input())):
	n = int(input())
	lol = [int(asdff) for asdff in input().split()]
	aaa = Counter(lol)
	gg = False
	cutoff = n + (n + 3) // 2
	for j in aaa.values():
		if j >= cutoff:
			gg = True
			break
	if gg == True:
		print('NO')
	else:
		print('YES')


for tea in range(int(input())):
	n = int(input())
	lol = [int(asdff) for asdff in input().split()]
	aaa = dict()
	for i in lol:
		if i in aaa:
			aaa[i] += 1
		else:
			aaa[i] = 1
	gg = False
	cutoff = n + (n + 3) // 2
	for j in aaa.values():
		if j >= cutoff:
			gg = True
			break
	print('NO' if gg else 'YES')


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = [0] * (2 * n + 5)
	for i in b:
		a[i] += 1
	mx = max(a)
	if mx > 2 * n - mx + 2 * (2 * n - mx + 1):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	for k in a:
		m = max(m, a.count(k))
	if m - n <= (n + 1) // 2:
		print('YES')
	else:
		print('NO')


from collections import Counter

def distinct():
	n = int(input())
	arr = list(map(int, input().split()))
	print('YES' if n * 2 - Counter(arr).most_common(1)[0][1] >= n // 2 else 'NO')
for _ in range(int(input())):
	distinct()


from collections import Counter
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	d = Counter()
	for n in A:
		d[n] += 1
	l = N + (N + 1) // 2
	f = True
	for v in d.values():
		if v > l:
			f = False
			break
	print('YES' if f else 'NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dict1 = {}
	for i in a:
		if i not in dict1:
			dict1[i] = 1
		else:
			dict1[i] += 1
	max1 = max(dict1.values())
	x = 2 * n - n // 2
	if max1 <= x:
		print('YES')
	else:
		print('NO')


from heapq import heappush, heappop, heapify
from collections import Counter

def solve(n, arr):
	h = [(-v, k) for (k, v) in Counter(arr).items()]
	heapify(h)
	total = 0
	while len(h) > 1:
		(count1, val1) = heappop(h)
		(count2, _) = heappop(h)
		count1 = -count1
		count2 = -count2
		total += count2
		if count1 - count2 > 0:
			heappush(h, (-(count1 - count2), val1))
	if h:
		if -h[0][0] // 2 <= total or -h[0][0] // 2 == total + 1:
			return 'YES'
		return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	my_list = input().split()
	a = [int(item) for item in my_list]
	hashMap = Counter(a)
	count = []
	for k in hashMap:
		count.append(hashMap[k])
	count.sort(reverse=True)
	rem = count[0]
	for i in count[1:]:
		rem = rem - i
	if rem >= n + 2:
		print('NO')
	else:
		print('YES')


from itertools import permutations
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from typing import Set
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def listinput(filename):
	return list(map(int, filename.readline().strip().split()))

def listinput_str(filename):
	return list(map(str, filename.readline().strip().split()))

def multiinput(filename):
	return map(int, filename.readline().strip().split())

def multiinput_str(filename):
	return map(str, filename.readline().strip().split())

def singleinput(filename):
	return int(filename.readline().strip())

def singleinput_str(filename):
	return filename.readline().strip()

def writeLine_space(l, filename):
	newl = []
	n = len(l)
	for i in range(n - 1):
		newl.append(str(l[i]))
		newl.append(' ')
	newl.append(str(l[n - 1]))
	newl.append('\n')
	filename.writelines(newl)

def writeLine_sep(l, filename):
	newl = []
	n = len(l)
	for i in range(n - 1):
		newl.append(str(l[i]))
		newl.append('\n')
	newl.append(str(l[n - 1]))
	newl.append('\n')
	filename.writelines(newl)
mod = 1000000007

def binSearchL(a, x):
	i = bl(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def binSearchR(a, x):
	i = br(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def getDivisors(n):
	i = 1
	li = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				li.append(i)
			else:
				li.append(i)
				li.append(int(n / i))
		i = i + 1
	li.sort()
	return li

def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def solve():
	n = inp()
	l = seq()
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	mxk = max(d.values())
	if mxk - n <= (n + 1) // 2:
		return 'YES'
	return 'NO'
t = inp()
for i in range(t):
	print(solve())


def solve():
	n = int(input())
	arr = [int(i) for i in input().split()]
	m = {}
	for i in arr:
		if i not in m.keys():
			m[i] = 0
		m[i] += 1
	limit = n + int((n + 1) / 2)
	for (key, value) in m.items():
		if value > limit:
			print('NO')
			return
	print('YES')
t = int(input())
while t:
	solve()
	t -= 1


from collections import Counter
from math import floor, ceil
test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	found = 1
	ct = Counter(a)
	for (i, j) in ct.items():
		if j > 2 * ceil(n / 2) + floor(n / 2):
			found = 0
			break
	if found:
		print('YES')
	else:
		print('NO')
	test -= 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max((a.count(x) for x in a))
	print('YES' if mx - n <= (n + 1) // 2 else 'NO')


for ii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	l = []
	if len(b) == len(a):
		print('YES')
	else:
		for i in b:
			l.append(a.count(i))
		x = max(l)
		if x - 2 <= 3 * (2 * n - x):
			print('YES')
		else:
			print('NO')


from collections import Counter
t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	k = 0
	(i, j) = (0, 2 * n - 1)
	l = []
	while i < j:
		l.append((-1) ** k * (a[i] - a[j]))
		i += 1
		j -= 1
		k += 1
	c = Counter(l)
	c1 = c.most_common(1)[0][1]
	if c1 <= (n + 1) // 2:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = n
	if n % 2 == 0:
		m += n // 2
	else:
		m += n // 2 + 1
	d = {}
	for i in a:
		d[i] = 0
	for i in a:
		d[i] += 1
	flag = 1
	for i in d:
		if d[i] > m:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	n = n * 2
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	maxx = 0
	for (i, j) in d.items():
		maxx = max(maxx, j)
	maxx = maxx - ((n - maxx + 1) * 2 + (n - maxx))
	if maxx > 0:
		print('NO')
	else:
		print('YES')


from collections import Counter
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l1 = []
	c = 1
	for i in range(1, 2 * n):
		if l[i] == l[i - 1]:
			c += 1
		else:
			l1.append(c)
			c = 1
	l1.append(c)
	s = max(l1)
	d = 2 * n - s
	x = s - d
	if x // 2 - d <= 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = [0] * (max(l) + 1)
	for i in l:
		c[i] += 1
	maximum = max(c)
	if n % 2 == 0:
		r = 3 / 2 * n
	if n % 2 != 0:
		n = n - 1
		r = 3 / 2 * n
		r = r + 2
	if maximum > r:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dict = {}
	maxi = 1
	for j in range(2 * N):
		if A[j] not in dict:
			dict[A[j]] = 1
		else:
			dict[A[j]] += 1
			maxi = max(maxi, dict[A[j]])
	List = []
	for (j, k) in dict.items():
		List.append(k)
	List.sort()
	n = len(List)
	if n == 1:
		print('NO')
	else:
		ans = 0
		for j in range(n - 1):
			ans += List[j]
		if List[-1] > 3 * ans + 2:
			print('NO')
		else:
			print('YES')


from collections import Counter
t = int(input())
for _ in range(t):
	(n, a) = (int(input()), list(map(int, input().split())))
	freq = Counter(a)
	max1 = max(freq.values())
	if n % 2 == 0:
		r = 1.5 * n
	else:
		n -= 1
		r = 1.5 * n
		r += 2
	if max1 > r:
		print('NO')
	else:
		print('YES')


def N():
	return int(input())

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

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'er9fj48gh48gh4' == 14194665565:
		print('Tanmay')
	a = A()
	a.sort()
	ar = []
	for i in range(n):
		ar.append(abs(a[n + i] - a[i]))
	z = ar.count(0)
	if z > n // 2 + n % 2:
		print('NO')
		continue
	print('YES')


def count(x):
	c = 0
	for i in lst:
		if i == x:
			c += 1
	return c

def exe():
	d = {}
	for i in lst:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		if d[i] > 1:
			break
	else:
		return 'YES'
	lst.sort()
	s = set(lst)
	l = [count(i) for i in s]
	maxi = 0
	for i in l:
		if maxi < i:
			maxi = i
	if maxi - 2 <= 3 * (sum(l) - maxi):
		return 'YES'
	return 'NO'
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


from collections import *
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(x, max) = map(int, Counter(l).most_common(1)[0])
	if n % 2 == 0:
		r = 3 / 2 * n
	else:
		n = n - 1
		r = 3 / 2 * n
		r = r + 2
	if max <= r:
		print('YES')
	else:
		print('NO')


from collections import Counter, defaultdict
import sys
import math

def sol(n, s):
	c = Counter(s)
	max_ = -1
	for i in c:
		if c[i] > max_:
			max_ = c[i]
	if n % 4 == 0:
		if max_ > 3 * n / 4:
			return 'NO'
	else:
		k = n // 4 + 1
		k = 2 * k + (n // 2 - n // 4 - 1)
		if max_ > k:
			return 'NO'
	return 'YES'
input = sys.stdin.readline

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

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

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	n = 2 * n
	s = inlt()
	s = s[:n]
	print(sol(n, s))


def findMajority(arr, n):
	maxCount = 0
	index = -1
	for i in range(n):
		count = 0
		for j in range(n):
			if arr[i] == arr[j]:
				count += 1
		if count > maxCount:
			maxCount = count
			index = i
	x = n / 2
	if maxCount <= n / 2 + (x + 1) / 2:
		print('YES')
	else:
		print('NO')
t = int(input())
while t > 0:
	n = int(input())
	n = 2 * n
	arr = [int(x) for x in input().split()]
	findMajority(arr, n)
	t -= 1


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	mx_count = 0
	d = Counter(arr)
	for i in d:
		mx_count = max(mx_count, d[i])
	left = mx_count
	if left > (2 * n - left) * 3 + 2:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = [0] * (max(l) + 1)
	for i in l:
		count[i] += 1
	m = max(count)
	if n % 2 == 0:
		req = 3 / 2 * n
	if n % 2 != 0:
		n = n - 1
		req = 3 / 2 * n
		req = req + 2
	if m > req:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = list(set(l))
	d = dict()
	n = n * 2
	for i in p:
		d[i] = 0
	for i in l:
		d[i] += 1
	a = max(d.values())
	if a > (n - a) * 3 + 2:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = 0
	for i in arr:
		c = arr.count(i)
		if c > x:
			x = c
	mp = x - n
	if mp > 2 * n - x + 1:
		print('NO')
	else:
		print('YES')


def fun(n, m):
	if m <= n:
		return 1
	return 0
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	c = 0
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
			c += 1
	m = 0
	for i in d:
		if d[i] > m:
			m = d[i]
	n = 2 * n
	n = int(n * 0.76)
	flag = fun(n, m)
	if flag == 1:
		print('YES')
	else:
		print('NO')


from collections import Counter
for test in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = dict(Counter(arr))
	max_occur = -1
	key = -1
	for i in cnt:
		if max_occur < cnt[i]:
			key = i
			max_occur = cnt[i]
	del cnt[key]
	if max_occur > n:
		temp = max_occur
		pairs = 0
		for i in cnt:
			pairs += cnt[i]
			temp -= cnt[i]
		if pairs + 1 < temp // 2:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


n = int(input())
for u in range(n):
	k = int(input())
	arr = list(map(int, input().split()))
	a = {}
	for i in range(2 * k):
		a[arr[i]] = 0
	for i in range(2 * k):
		a[arr[i]] += 1
	aa = []
	ma = 0
	for kk in a:
		ma = max(ma, a[kk])
		aa.append(a[kk])
	s = sum(aa) - ma
	if ma - s < 0:
		print('YES')
	elif s + 1 < (ma - s) // 2:
		print('NO')
	else:
		print('YES')


import math
for t in range(int(input())):
	num = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	i = 0
	j = 2 * num - 1
	order = 1
	b = []
	while i < j:
		if order % 2 == 0:
			b.append(abs(nums[j] - nums[i]))
		else:
			b.append(abs(nums[i] - nums[j]) * -1)
		order += 1
		i += 1
		j -= 1
	d = {}
	for i in b:
		d[i] = d.get(i, 0) + 1
	d = list(sorted(d.items(), key=lambda x: -x[1]))
	if d[0][1] <= (num + 1) / 2:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	i = 0
	j = 2 * n - 1
	f = 1
	b = []
	while i < j:
		if f % 2 == 0:
			b.append(abs(arr[j] - arr[i]))
		else:
			b.append(abs(arr[i] - arr[j]) * -1)
		f += 1
		i += 1
		j -= 1
	d = {}
	for i in b:
		d[i] = d.get(i, 0) + 1
	d = list(sorted(d.items(), key=lambda x: -x[1]))
	if d[0][1] <= (n + 1) / 2:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = Counter(map(int, input().split())).most_common()[0][1]
	if 2 * s > 3 * n + 1:
		print('NO')
	else:
		print('YES')


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict(Counter(a))
	l = []
	for i in d:
		l.append(d[i])
	l = sorted(l, reverse=True)
	g = sum(l)
	x = g * 0.76
	h = l[0]
	x = int(x)
	if h <= x:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	size = int(input())
	L = list(map(int, input().split()))
	C = Counter(L)
	n = size // 2
	if len(C) >= n + 1:
		print('YES')
		continue
	else:
		L = list(C.values())
		x = max(L)
		if size * 2 - x >= n:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	n1 = n // 2
	l = list(map(int, input().split()))
	s = set(l)
	l.sort()
	le = len(l)
	i = 0
	j = le - 1
	new = []
	flag = 0
	while i < j:
		if flag == 0:
			dif = l[j] - l[i]
			flag = 1
		else:
			dif = l[i] - l[j]
			flag = 0
		i += 1
		j -= 1
		new.append(dif)
	d = dict()
	mx = 0
	for k in new:
		if k not in d:
			d[k] = 0
		d[k] += 1
		if d[k] > mx:
			mx = d[k]
	zz = (n + 1) // 2
	if mx <= zz:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in range(2 * n):
		d[arr[i]] += 1
	ans = 0
	for x in list(d.keys()):
		ans = abs(ans - d[x])
	ans = ans // 2
	val = n // 2 + n % 2
	if ans > val:
		print('NO')
	else:
		print('YES')


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	d = {}
	for i in l:
		try:
			d[i] += 1
		except:
			d[i] = 1
	(s, m) = (0, 0)
	for i in d:
		if d[i] > m:
			m = d[i]
		s += d[i]
	t = s - m
	if m > t * 3 + 2:
		pr('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = {}
	for i in range(len(a)):
		if a[i] in m:
			m[a[i]] += 1
		else:
			m[a[i]] = 1
	ans = 0
	for i in m.keys():
		ans = max(ans, m[i])
	if ans > n:
		left = ans - (2 * n - ans)
		left /= 2
		if 2 * n - ans + 1 >= left:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	val = (3 * n + 1) // 2
	di = {}
	for item in nums:
		if item in di:
			di[item] += 1
		else:
			di[item] = 1
	maxi = -1
	for key in di:
		if di[key] > maxi:
			maxi = di[key]
	if maxi > val:
		print('NO')
	else:
		print('YES')


import sys, math, random

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

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(sys.stdin.readline())
for t2 in range(t):
	n = int(input())
	a = get_arr()
	y = 1
	x = 0
	fl = 0
	for i in range(10 ** 3):
		random.shuffle(a)
		hq = {}
		ma = 0
		for i in range(n):
			val = a[2 * i] - a[2 * i + 1]
			if val in hq.keys():
				hq[val] += 1
				ma = max(ma, hq[val])
			else:
				hq[val] = 1
		if ma <= (n + 1) // 2:
			print('YES')
			fl = 1
			break
	if fl == 0:
		print('NO')


from collections import deque
from math import ceil, sqrt

def isSorted(arr):
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			return 0
	return 1

def func(arr, n):
	used = [0] * (2 * n)
	eq = 1
	d = {}
	for i in range(2 * n):
		if arr[i] in d:
			d[arr[i]] += 1
		else:
			d[arr[i]] = 1
	m = 0
	for i in d.values():
		if i > m:
			m = i
	zc = m // 2
	matched = len(arr) - m
	zc = (m - matched) // 2
	if zc > matched + 1:
		return 0
	return 1

def primeFactors(n, m):
	factors = set()
	while n % 2 == 0:
		(factors.add(2),)
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			(factors.add(i),)
			n = n / i
	if n > 2:
		factors.add(n)
	A = 1
	for i in factors:
		A *= i
	return A
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = func(arr, n)
	if ans:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s.sort()
	res = []
	for i in range(n):
		if i % 2 == 0:
			res.append(s[i] - s[2 * n - i - 1])
		else:
			res.append(s[2 * n - 1 - i] - s[i])
	x = Counter(res).most_common(1)[0][1]
	if x <= (n + 1) // 2:
		print('YES')
	else:
		print('NO')