429_C. Guess the Tree
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 ci 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 ci (1 ≤ ci ≤ 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
```python
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]
            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)
            

```