Chef is hosting a party at his house and N people are invited to it. Everyone has arrived and they are eager to make a group and chit-chat.

The i^{th} person prefers to be in a group of exactly P_{i} people (including himself). A person who is not in a group of preferred size gets upset. Find whether Chef would be able to assign every person to a group such that everyone remains happy.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of people at the party.
- The next line contains the array P — where P_{i} denotes the preferred group size for i^{th} person.

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

For each test case, output YES, if Chef can assign every person to a group such that everyone remains happy. Otherwise output NO.

The output is case-insensitive, meaning that outputs such as yES, YeS, YES and yes mean the same.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$2 ≤ P_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

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

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

----- explanation 1 ------ 
Test case $1$:
- Person $1$ and $3$ can make a group (As both want to be in a group of $2$).
- Person $2$, $4$ and $5$ can make a group (As they all want to be in a group of $3$).

So, there is a possible arrangement that Chef can make so that all of them are happy.

Test case $2$:
- All of the $5$ people can make a group (As all want to be in a group of $5$).

So, there is a possible arrangement that Chef can make so that all of them are happy.

Test case $3$: It can be shown that there is no possible arrangement that Chef can make so that all of them are happy.

Test case $4$: It can be shown that there is no possible arrangement that Chef can make so that all of them are happy.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = set(l)
	for j in m:
		if l.count(j) % j != 0:
			print('NO')
			break
	else:
		print('YES')


T = int(input())
while T > 0:
	N = int(input())
	P = list(map(int, input().split()))
	s = set(P)
	for i in s:
		if P.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')
	T -= 1


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	s = set(p)
	for i in s:
		if p.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	groups = set(l)
	ans = 'YES'
	for i in groups:
		if l.count(i) % i != 0:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = list(set(l))
	c = 0
	for i in s:
		if l.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	Length = int(input())
	li = list(map(int, input().split()))
	sets = set(li)
	for i in sets:
		if li.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = set(arr)
	for i in m:
		if arr.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	groups = set(p)
	for g in groups:
		if p.count(g) % g != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	d = {}
	for num in s:
		if num in d:
			d[num] = d[num] + 1
		else:
			d[num] = 1
	stop = 0
	for key in d:
		if d[key] % key != 0:
			print('NO')
			stop = 1
			break
	if stop == 0:
		print('YES')


for i in range(int(input())):
	x = int(input())
	v = list(map(int, input().split()))
	c = 0
	a = set(v)
	for i in a:
		if v.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()[:n]))
	l = set(p)
	for i in l:
		if p.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	s = set(A)
	for i in s:
		if A.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	g = set(p)
	for j in g:
		if p.count(j) % j != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set()
	f = 1
	for i in l:
		s.add(i)
	for i in s:
		if l.count(i) % i == 0:
			continue
		else:
			f = 0
			print('NO')
			break
	if f:
		print('YES')


test_cases = int(input())
for i in range(test_cases):
	n = int(input())
	group = list(map(int, input().split()))[:n]
	gs = set(group)
	gl = list(gs)
	count = 0
	for i in gl:
		c = group.count(i)
		if c % i == 0:
			count = count + 1
	if count == len(gs):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = set(l)
	for i in g:
		if l.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	s = set(p)
	flag = 0
	for i in s:
		if p.count(i) % i != 0:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	prr = list(map(int, input().split()))
	groups = set(prr)
	for i in groups:
		if prr.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
while t:
	n = int(input())
	p = list(map(int, input().split()))
	group = set(p)
	for g in group:
		if p.count(g) % g != 0:
			print('NO')
			break
	else:
		print('YES')
	t -= 1


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict(Counter(l))
	b = 1
	for (i, j) in d.items():
		if j % i != 0:
			b = 0
			break
	if b:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = set(l)
	c = 0
	for j in k:
		if l.count(j) % j != 0:
			c = 1
			break
	if c == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	n_p = input().split(' ')
	s_p = set(n_p)
	for p in s_p:
		count = 0
		for j in range(n):
			if n_p[j] == p:
				count += 1
		if count % int(p) != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(str, input().split()))
	s = set(a)
	for j in s:
		if a.count(j) % int(j) != 0:
			print('NO')
			break
	else:
		print('YES')


from collections import Counter
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = 0
	d = Counter(l)
	for i in d:
		if d[i] % i != 0:
			s += 1
			break
	if s == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	sets = set(arr)
	for k in sets:
		if arr.count(k) % k != 0:
			print('NO')
			break
	else:
		print('YES')


for j in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = set(b)
	for i in c:
		if b.count(i) % i != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
while t > 0:
	n = int(input())
	ls = list(map(int, input().split()))
	for i in set(ls):
		x = ls.count(i)
		if x % i != 0:
			print('NO')
			break
	else:
		print('YES')
	t -= 1


a = int(input())
for i in range(a):
	b = int(input())
	l = list(map(int, input().split()))
	x = set(l)
	c = 1
	for i in x:
		if l.count(i) % i != 0:
			c = 0
			break
	if c == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	l = int(input())
	a = [int(x) for x in input().split()]
	ans = 'YES'
	for i in set(a):
		if a.count(i) % i != 0:
			ans = 'NO'
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = d = 0
	for i in set(a):
		if a.count(i) % i != 0:
			d = 1
			break
	if d == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	p.sort(reverse=True)
	check = 1
	for item in set(p):
		if p.count(item) % item != 0:
			print('NO')
			check = 0
			break
	if check:
		print('YES')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	bl = True
	for i in s:
		cn = a.count(i)
		if cn % i != 0:
			bl = False
	if bl:
		print('YES', end='\n')
	else:
		print('NO', end='\n')
	t = t - 1


t = int(input())
while t != 0:
	n = int(input())
	c = True
	p = list(map(int, input().split()))
	s = set(p)
	for i in s:
		if p.count(i) % i != 0:
			c = False
	if c:
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	p = tuple(map(int, input().split()))
	s = set(p)
	flag = True
	for i in s:
		if p.count(i) % i != 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 'YES'
	for i in set(a):
		if a.count(i) % i != 0:
			c = 'NO'
			break
	print(c)


def assignment(number, arr):
	original_data = list(set(arr))
	for i in original_data:
		k = arr.count(i)
		if k % i != 0:
			return 'NO'
	return 'YES'
for i in range(int(input())):
	number = int(input())
	arr = [int(i) for i in input().split()]
	print(assignment(number, arr))


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = list(map(int, input().split()))
	death = set(life)
	for aim in death:
		if life.count(aim) % aim != 0:
			print('NO')
			break
	else:
		print('YES')