Are you fond of collecting some kind of stuff? Mike is crazy about collecting stamps. He is an active member of Stamp Collecting Сommunity(SCC). 

SCC consists of N members which are fond of philately. A few days ago Mike argued with the others from SCC. Mike told them that all stamps of the members could be divided in such a way that i'th member would get i postage stamps. Now Mike wants to know if he was right. The next SCC meeting is tomorrow. Mike still has no answer.

So, help Mike! There are N members in the SCC, i'th member has Ci stamps in his collection. Your task is to determine if it is possible to redistribute C1 + C2 + ... + Cn stamps among the members of SCC thus that i'th member would get i stamps.

-----Input-----
The first line contains one integer N, denoting the number of members of SCC.
The second line contains N integers Ci, denoting the numbers of the stamps in the collection of i'th member.

-----Output-----
The first line should contain YES, if we can obtain the required division, otherwise NO.

-----Constraints-----
1 ≤ N ≤ 100 000;
1 ≤  Ci ≤ 109.

-----Examples-----
Input:
5
7 4 1 1 2

Output:
YES

Input:
5
1 1 1 1 1

Output:
NO

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n=int(input())
s=list(map(int,input().split()))
su=0
for i in s:
    su+=i

an=(n)*(n+1)//2
if(an==su):
    print("YES")

else:
    print("NO")


n = int(input())
# s = n*(n+1)/2

stamps = list(map(int, input().split()))
# print(s)
# print(sum(stamps))
if (n*(n+1))/2 == sum(stamps):
    print("YES")
else:
    print("NO")

# cook your dish here
n = int(input())
nums = list(map(int, input().split()))
print("YES" if (n*(n+1))/2 == sum(nums) else "NO")

# cook your dish here
try:        
    n = int(input())
    stampArr = list(map(int, input().split()))
    nsum = sum(range(1, n+1))
    ssum = sum(stampArr)
    if nsum == ssum:
        print("YES")
    else:
        print("NO")
except:
    pass

N=int(input())
L=list(map(int,input().split()))[:N]
if sum(L)==N*(N+1)/2:
    print("YES")
else:
    print("NO")

N=int(input())
L=list(map(int,input().split()))[:N]
if sum(L)==N*(N+1)/2:
    print("YES")
else:
    print("NO")


try:
    N = int(input())
    lst = sorted(list(map(int, input().split())))
    sum=0
    for i in range(N):
        sum=sum+lst[i]
    sum2=0
    for i in range(1,N+1):
        sum2=sum2+i
    if sum2==sum:print("YES")
    else:print("NO")
except:
    pass
# cook your dish here


# cook your dish here
n=int(input())
a=list(map(int, input().split()))

x=0
for i in range(n+1):
    x=x+i

add=sum(a)
if(x==add):
    print('YES')
else:
    print('NO')
    

# cook your dish here
n=int(input())
a=list(map(int, input().split()))

x=0
for i in range(n+1):
    x=x+i

add=sum(a)
if(x==add):
    print('YES')
else:
    print('NO')
    

n=int(input())
l=list(map(int,input().split()))
sums=0
for i in range(n+1):
    sums+=i
a=sum(l)
if a==sums:
    print('YES')
else:
    print('NO')
    
    
    

n = int(input())
A = list(map(int,input().split()))
add = sum(A)
req = (n*(n+1))//2;
if(add==req) : print("YES")
else : print("NO")

def main():
    n=int(input())
    l1=list(map(int,input().split()))
    N=(n*(n+1))/2
    sum1=0
    for i in range(n):
        sum1+=l1[i]
    if(sum1==N):
        print("YES")
    else:
        print("NO")
        
        
main()

n = int(input())

stamps = list(map(int,input().split()))

if(sum(stamps) == (n*(n+1))/2):
    print("YES")
else:
    print("NO")

# cook your dish here
n=int(input())
stamps=list(map(int,input().split()))
if n*(n+1)/2==sum(stamps):
    print("YES")
else :
    print("NO")

# cook your dish here

n=int(input())
stamps=list(map(int,input().split()))
if n*(n+1)/2==sum(stamps):
    print("YES")
else :
    print("NO")
    
    

n = int(input())
s =0
l = list(map(int,input().split()))
for i in range(1,n+1):
    s = s+i
p = sum(l)
if(sum(l) == s):
    print("YES")
else:
    print("NO")
    


# cook your dish here
l = []
n = int(input())
x = map(int, input().split())
x1 = sum(x)
for i in range(1, n+1):
    l.append(i)

l1 = sum(l)
if x1 == l1:
    print("YES")
else:
    print("NO")

# cook your dish here
l=list()
n=int(input())
x=[int(item) for item in input().split()]
sum1=sum(x)
j=1
while n:
    l.append(j)
    j=j+1
    n=n-1
if sum1==sum(l)    :
    print("YES")
else:
    print("NO")
    


n = int(input())
s = 0
l = list(map(int,input().split()))
for i in l:
    s+= i
if ((n*(n+1))/2)==s:
    print("YES")
else:
    print("NO")

# cook your dish here
import math
n=int(input())
l=list(map(int,input().split()))
s=sum(l)
z=math.trunc(math.sqrt(1+8*s))
z=(-1+z)//2
if z==n:
    print("YES")
else:
    print("NO")

n = int(input())
arr = list(map(int, input().split()))
s1 = sum(arr)
s2 = n * (n+1) / 2
if s1 == s2:
    print('YES')
else:
    print('NO')

n = int(input())

L = [int(x) for x in input().split()]

s = sum(L)

if s == n*(n+1)//2:
    print('YES')

else:
    print('NO')

# cook your dish heretry
try:
    n=int(input())
    l=[int(x) for x in input().split()]
    if((n*(n+1)//2)==sum(l)):
        print("YES")
    else:
        print("NO")
except:
    pass


n=int(input())
l=list(map(int,input().strip().split()))
s=sum(l)
k=0
for i in range(0,len(l)+1):
    k=k+i

if s==k:
    print("YES")
else:
    print("NO")

# cook your dish here
t=int(input())
a=list(map(int,input().split()))[:t]
b=(t*(t+1))//2
c=sum(a)
if(b==c):
    print("YES")
else:
    print("NO")