You are given an array $a_1, a_2, \ldots, a_n$.

In one operation you can choose two elements $a_i$ and $a_j$ ($i \ne j$) and decrease each of them by one.

You need to check whether it is possible to make all the elements equal to zero or not.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.


-----Output-----

Print "YES" if it is possible to make all elements zero, otherwise print "NO".


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

Output
YES
Input
6
1 2 3 4 5 6

Output
NO


-----Note-----

In the first example, you can make all elements equal to zero in $3$ operations:   Decrease $a_1$ and $a_2$,  Decrease $a_3$ and $a_4$,  Decrease $a_3$ and $a_4$ 

In the second example, one can show that it is impossible to make all elements equal to zero.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

n = getN()
nums = getList()

if sum(nums) % 2 == 1:
    print("NO")
    return

if max(nums) * 2 > sum(nums):
    print("NO")
    return

print("YES")


n = int(input())
a = [*list(map(int,input().split()))]
sa = sum(a)
ma = max(a)
print("YNEOS"[(sa % 2 or ma > sa - ma)::2])


def main():
    import sys
    input = sys.stdin.readline
    
    n = int(input())
    arr = list(map(int, input().split()))
    
    ma = max(arr)
    s = sum(arr)
    
    if ma * 2 > s or (s & 1):
        print("NO")
    else:
        print("YES")
    
    return 0

main()

n = int(input())
A = [int(x) for x in input().split()]
mx = max(A)

if mx <= sum(A) - mx and sum(A)%2 == 0:
    print('YES')
else:
    print('NO')


n = int(input())
a = list(map(int, input().split()))
sum1 = sum(a)
max1 = max(a)
if sum1 % 2 == 0 and sum1 - max(a) >= max(a):
    print("YES")
else:
    print("NO")

n = int(input())
a= list(map(int,input().split()))
#print(sum(a), max(a))
if(sum(a) < 2*max(a) or sum(a)%2 == 1):
    print('NO')
else:
    print('YES')

n = int(input())
arr = [int(s) for s in input().split()]
s = sum(arr)
if s % 2 == 0 and max(arr) * 2 <= s:
    print('YES')
else:
    print('NO')

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
v = True
if 2 * max(a) > sum(a):
    v = False
if sum(a) % 2 == 1:
    v = False
if v == True:
    print("YES")
else:
    print("NO")

n=int(input())
a=[int(x) for x in input().split()]
s=sum(a)
if max(a)<=s-max(a) and s%2==0:
    print('YES')
else:
    print('NO')


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

if sum(A)%2==0 and max(A)<=sum(A)-max(A):
    print("YES")
else:
    print("NO")


n = input()
a = list(map(int, input().split()))
print('YES' if sum(a)%2==0 and 2*max(a)<=sum(a) else 'NO')


import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int, input().split()))
s = sum(l)
if s % 2 == 1:
	print("NO")
else:
	if max(l) > s // 2:
		print("NO")
	else:
		print("YES")

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)

if (sum(a) % 2 == 0 and sum(a[:-1]) >= a[-1]):
    print("YES")
else:
    print("NO")


n=int(input())
a=list(map(int,input().split()))
if sum(a)%2:
    print("NO")
else:
    a.sort()
    if sum(a[:n-1])-a[-1]<0:
        print("NO")
    else:    
        print("YES")

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
sm = sum(arr)
if ((arr[-1] * 2) <= sm) and (sm % 2 == 0):
    print("YES")
else:
    print("NO")



n = int(input())
s = list(map(int, input().split()))
x = sum(s)
if x % 2 == 1:
	print("NO")
else:
	for c in s:
		if c > x - c:
			print("NO")
			return
	print("YES")


n = int(input())
a = list(map(int,input().split()))
s = 0
for i in a:
    s+=i
if s-max(a)*2<0:
    print('NO')
elif s%2==0:
    print('YES')
else:
    print('NO')

n = int(input())
l = list(map(int, input().rstrip().split()))

s = sum(l)
ma = max(l)
if (s % 2 == 0) and (ma <= s/2):
    print("YES")
else:
    print("NO")

n = int(input())
ai = list(map(int,input().split()))
num = sum(ai)
if num % 2 == 0:
    if sum(ai) < 2 * max(ai):
        print("NO")
    else:
        print("YES")
else:
    print("NO")


n = int(input())
b = list(map(int, input().strip().split()))
m = 0
s = 0
can = True
for i in b:
    m = max(m,i)
    s += i
if s%2:
    can = False
if 2*m > s:
    can = False
if can:
    print ('YES')
else:
    print ('NO')

[n] = [int(w) for w in input().split()]
a = [int(w) for w in input().split()]

t = max(a)
s = sum(a)
r = s % 2 == 0 and s >= 2*t
print("YES" if r else "NO")


#577_B

n = int(input())

ln = [int(i) for i in input().split(" ")]

s = 0
m = 0
for i in ln:
    s += i
    m = max(m, i)

if s % 2 == 1:
    print("NO")
else:
    if m <= s / 2:
        print("YES")
    else:
        print("NO")


a = int(input())
A = list(map(int,input().split()))
m = max(A)
s = sum(A)
if s-m>=m and s%2==0:
    print('YES')
else:
    print('NO')


n = int(input())
assert(2 <= n <= 100000)

li = list(map(int, input().split()))
su = sum(li)
if su % 2 == 0:
    # check that every element is balanced
    for item in li:
        if su < item << 1:
            print("NO")
            break
    else:
        print("YES")
else:
    print("NO")