430_E. 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]

            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)

            





# Made By Mostafa_Khaled
```