Iahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food. 

Iahub asks Iahubina: can you build a rooted tree, such that

  each internal node (a node with at least one son) has at least two sons;  node i has c_{i} nodes in its subtree? 

Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain n nodes.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 24). Next line contains n positive integers: the i-th number represents c_{i} (1 ≤ c_{i} ≤ n).


-----Output-----

Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes). 


-----Examples-----
Input
4
1 1 1 4

Output
YES
Input
5
1 1 5 2 1

Output
NO

Source: codeforces | Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Greedy algorithms

Tree algorithms

Dynamic programming


Solutions:
def DFS(x):
	for i in range(x):
		if Seen[i][x]:
			continue
		if Rem[i] >= C[x]:
			if Rem[i] == C[x] and len(Children[i]) == 0:
				continue
			Rem[i] -= C[x]
			Parent[x] = i
			Children[i].append(x)
			return True
	for i in range(x):
		if Seen[i][x]:
			continue
		Y = []
		for j in range(len(Children[i])):
			child = Children[i][j]
			if Seen[i][child]:
				continue
			Parent[child] = -1
			Rem[i] += C[child]
			Seen[i][child] = True
			Seen[child][i] = True
			if DFS(child):
				Seen[i][child] = False
				Seen[child][i] = False
				continue
			Seen[i][child] = False
			Seen[child][i] = False
			Parent[child] = i
			Rem[i] -= C[child]
			Y.append(child)
		Children[i] = list(Y)
		if Rem[i] >= C[x]:
			if Rem[i] == C[x] and len(Children[i]) == 0:
				continue
			Rem[i] -= C[x]
			Children[i].append(x)
			Parent[x] = i
			return True
	return False
n = int(input())
C = list(map(int, input().split()))
Rem = [-1] * n
Parent = [-1] * n
Children = []
Seen = []
for i in range(n):
	Seen.append([False] * n)
C.sort(reverse=True)
if C[0] != n or C.count(2) > 0:
	print('NO')
else:
	for i in range(n):
		Rem[i] = C[i] - 1
		Children.append([])
	Parent[0] = 0
	Ans = 'YES'
	for i in range(1, n):
		if DFS(i) == False:
			Ans = 'NO'
			break
	for i in range(n):
		if Rem[i] != 0 and C[i] != 1:
			Ans = 'NO'
			break
	print(Ans)