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

Difficulty: competition

Starter code:

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]
            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)
            


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)
            


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