Vasya has an array a consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).

Inserting an element in the same position he was erased from is also considered moving.

Can Vasya divide the array after choosing the right element to move and its new position?


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 100000) — the size of the array.

The second line contains n integers a_1, a_2... a_{n} (1 ≤ a_{i} ≤ 10^9) — the elements of the array.


-----Output-----

Print YES if Vasya can divide the array after moving one element. Otherwise print NO.


-----Examples-----
Input
3
1 3 2

Output
YES

Input
5
1 2 3 4 5

Output
NO

Input
5
2 2 3 4 5

Output
YES



-----Note-----

In the first example Vasya can move the second element to the end of the array.

In the second example no move can make the division possible.

In the third example Vasya can move the fourth element by one position to the left.

Difficulty: interview

Starter code:

Solutions:
def solve(n,a):
    tot=0
    for i in range(n):
        tot+=a[i]
    diffs = [] #alla suffix - prefix diffs[i]=prefix-suffix om delas innan element i
    diffs.append(-tot)
    for i in range(n):
        tot-=2*a[i]
        diffs.append(-tot)
        if tot==0:
            return ("YES")
    for i in range(n):
        diffmake=2*a[i]
        j=binary(diffs,diffmake)
        if j>i and j!=-1:
            return ("YES")
        j=binary(diffs,-diffmake)
        if i>=j and j!=-1:
            return ("YES")
    return ("NO")


def binary(a,value):
    hi=len(a)
    lo=-1
    while (lo+1<hi):
        mi=(lo+hi)//2
        if a[mi]==value:
            return mi
        if a[mi]<value:
            lo=mi
        else:
            hi=mi
    return -1


n=int(input())
a = input().split()
for i in range (n):
    a[i]=int(a[i])
print(solve(n,a))


def solve():
    n = int(input())
    #n, w = map(int, input().split())
    a = list(map(int, input().split()))
    #a = [list(map(int, input().split())) for _ in range(n)]
    ok = 0
    Su = sum(a)
    di = dict()
    di[0] = 1
    su = 0
    for i in range(n):
        su += a[i]
        if di.get(a[i] * 2, 0) == 0:
            di[a[i] * 2] = 1
        if di.get(su - Su + su, 0) == 0:
            pass
        else:
            ok = 1
    di.clear()
    di[0] = 1
    su = 0
    for i in range(-1, -n - 1, -1):
        su += a[i]
        if di.get(a[i] * 2, 0) == 0:
            di[a[i] * 2] = 1
        if di.get(su - Su + su, 0) == 0:
            pass
        else:
            ok = 1
    if ok:
        print('YES')
    else:
        print('NO')

def __starting_point():
    solve()
__starting_point()

def mp():  return list(map(int,input().split()))
def lt():  return list(map(int,input().split()))
def pt(x):  print(x)
def ip():  return input()
def it():  return int(input())
def sl(x):  return [t for t in x]
def spl(x): return x.split()
def aj(liste, item): liste.append(item)
def bin(x):  return "{0:b}".format(x)
def listring(l): return ' '.join([str(x) for x in l])
def ptlist(l): print(' '.join([str(x) for x in l]))

n = it()
a = lt()
k = 0
left = 0
right = sum(a)
bl = False
dict = {}
for i in range(n):
    if a[i] in dict:
        (ma,mi) = dict[a[i]]
        dict[a[i]] = (max(ma,i),min(mi,i))
    else:
        dict[a[i]] = (i,i)
while k < n and not bl:
    if right == left:
        bl = True
    elif right > left:
        x = (right-left)/2
        if x == int(x) and int(x) in dict and dict[int(x)][0] >= k:
            bl = True
        else:
            right -= a[k]
            left += a[k]
            k += 1
    else:
        x = (left-right)/2
        if x == int(x) and int(x) in dict and dict[int(x)][1] <= k-1:
            bl = True
        else:
            right -= a[k]
            left += a[k]
            k += 1
if bl:
    pt("YES")
else:
    pt("NO")
            
            


def solve(a):
    s = sum(a)
    if s % 2 == 1:
        return False
    s //= 2

    elements = set()
    cs = 0
    n = len(a)

    for i in range(n):
        cs += a[i]
        if cs == s:
            return True

        elements.add(a[i])

        if i > 0 and cs > s and cs - s in elements:
            return True

    return False


def main():
    n = int(input())
    a = list(map(int, input().split()))

    if solve(a):
        print("YES")
    elif solve(a[::-1]):
        print("YES")
    else:
        print("NO")


def __starting_point():
    # import sys
    # sys.stdin = open("in.txt")
    main()

__starting_point()


# Python Interpreter Version: Python 3.5.2
#
# Note: Educational Codeforces Round 21

def divPos(arr):
    sumArr = sum(arr)
    targetSum = sumArr / 2
    if sumArr % 2 != 0:
        return False
    lArr = set()
    sumlArr = 0
    for i in range(len(arr)):
        lArr.add(arr[i])
        sumlArr += arr[i]
        if sumlArr == targetSum or (sumlArr > targetSum and sumlArr - targetSum in lArr):
            return True
    return False

def __starting_point():
    n = input()
    arr = [int(x) for x in input().split()]
    # arr = [2,2,3,4,5]
    if divPos(arr) or divPos(arr[::-1]):
        print('YES')
    else:
        print('NO')

__starting_point()

import math
import re

def f(arr, n):
    a = set()
    x = 0
    y = sum(arr)
    res = 'NO'
    for i in range(n):
        x += arr[i]
        y -= arr[i]
        a.add(arr[i])
        q = x - y

        if q % 2 != 0:
            continue
        elif q == 0 or (q > 0 and q / 2 in a):
            res = 'YES'
            break
    return res

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

res = f(arr, n)
if res == 'NO':
    arr = arr[::-1]
    res = f(arr, n)

print(res)

    # arr = list(map(int, input().split()))
# res = 0
# a = {math.pow(2, i) for i in range(35)}
# for i in range(n-1):
#     for j in range(i+1,n):
#         if arr[i] + arr[j] % 2 % 2 % 2 % 2 % 2 in a:
#             res += 1
#
# print(res)


# arr = list(map(int, input().split()))
# m = int(input())
# spis = list(map(int, input().split()))
#
# arr1 = sorted(arr, reverse=True)
# a = [n - arr1.index(arr[el - 1]) for el in spis]
# print(' '.join(map(str, a)))


import sys
from itertools import accumulate

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]

    S = sum(a)

    if S & 1:
        print('NO')
        return

    f_a = dict()
    l_a = dict()

    for i in range(n):
        if a[i] not in f_a:
            f_a[a[i]] = i

    for i in range(n - 1, -1, -1):
        if a[i] not in l_a:
            l_a[a[i]] = i

    ps = [0] + list(accumulate(a))
    S //= 2

    for k in range(1, n + 1):
        x = S - ps[k]

        if x == 0:
            print('YES')
            return
        elif x > 0:
            if x in l_a and k <= l_a[x]:
                print('YES')
                return
        else:
            x *= -1
            
            if x in f_a and f_a[x] < k:
                print('YES')
                return

    print('NO')


def __starting_point():
    solve()
__starting_point()

import sys
from itertools import accumulate

def solve():
    n = int(input())
    a = [int(i) for i in input().split()]

    S = sum(a)

    if S & 1:
        print('NO')
        return

    S //= 2

    ap = set()
    ps = [0] + list(accumulate(a))

    for i in range(1, n + 1):
        x = ps[i] - S
        ap.add(a[i - 1])

        if x == 0 or x in ap:
            print('YES')
            return

    ap = set()
    a = a[::-1]
    ps = [0] + list(accumulate(a))

    for i in range(1, n + 1):
        x = ps[i] - S
        ap.add(a[i - 1])

        if x == 0 or x in ap:
            print('YES')
            return

    print('NO')

def __starting_point():
    solve()
__starting_point()

n = int(input())
arr = [int(x) for x in input().split()]
if n==1:
	print("NO")
	return
s = sum(arr)
sp = 0
ss = s
setq = {}
setp = {}
for i in arr:
	setq[i] = setq.get(i,0)+1
	setp[i] = 0
for i in range(n):
	sp += arr[i]
	ss -= arr[i]
	setp[arr[i]] += 1
	setq[arr[i]] -= 1
	val = ss-sp
	if val>0 and not val&1:
		val //= 2
		ans = setq.get(val,0)
		if ans>0:
			print("YES")
			return
	elif val<0 and not (-val)&1:
		val = -val
		val //= 2
		ans = setp.get(val,0)
		if ans>0:
			print("YES")
			return
	elif val==0:
		print("YES")
		return
print("NO")


class Dick:
    def __init__(self):
        self.s = 0
        self.m = dict()
    def add(self, x):
        self.s += x
        if x in self.m:
            self.m[x] += 1
        else:
            self.m[x] = 1
    def rm(self, x):
        self.s -= x
        if self.m[x] > 1:
            self.m[x] -= 1
        else:
            self.m.pop(x)
    def shasei(self):
        return self.s
    def ininder(self, x):
        return x in self.m
def ok(a,n):
    w = sum(a)
    if w & 1:
        return 0
    f = Dick()
    s = Dick()
    for x in a:
        s.add(x)
    w //= 2
    for i in range(n):
        if s.ininder(w - f.shasei()) or f.ininder(w - s.shasei()):
            return 1
        f.add(a[i])
        s.rm(a[i])
    return 0

n = int(input())
a = list(map(int, input().split()))
print("YES" if ok(a,n) else "NO")

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


def solve(a):
    rtn = False
    tmp = 0
    dic = {}
    for i in range(n):
        tmp += a[i]
        dic[a[i]] = True
        if tmp == s // 2:
            rtn = True
            break
        elif s // 2 < tmp and (tmp - s // 2) in dic:
            rtn = True
            break
    return rtn


if n == 1 or s % 2 == 1:
    print('NO')
elif solve(a) or solve(list(reversed(a))):
    print('YES')
else:
    print('NO')


def solve(n,a):
    tot=0
    for i in range(n):
        tot+=a[i]
    diffs = [] #alla suffix - prefix diffs[i]=prefix-suffix om delas innan element i
    diffs.append(-tot)
    for i in range(n):
        tot-=2*a[i]
        diffs.append(-tot)
        if tot==0:
            return ("YES")
    for i in range(n):
        diffmake=2*a[i]
        j=binary(diffs,diffmake)
        if j>i and j!=-1:
            return ("YES")
        j=binary(diffs,-diffmake)
        if i>=j and j!=-1:
            return ("YES")
    return ("NO")


def binary(a,value):
    hi=len(a)
    lo=-1
    while (lo+1<hi):
        mi=(lo+hi)//2
        if a[mi]==value:
            return mi
        if a[mi]<value:
            lo=mi
        else:
            hi=mi
    return -1


n=int(input())
a = input().split()
for i in range (n):
    a[i]=int(a[i])
print(solve(n,a))

import sys
from bisect import bisect_left, bisect_right

# sys.stdin = open("in", "r")


def find(arr, x):
    i1 = bisect_left(arr, x)
    i2 = bisect_right(arr, x)
    if(i1 < len(arr) and arr[i1] == x):
        return i1, i2 - 1
    else:
        return -1


n = int(input())

arr = [(i, int(x)) for i, x in enumerate(input().split())]
cum = []
for i in range(n):
    if(i == 0):
        cum.append(arr[i][1])
    else:
        cum.append(cum[i - 1] + arr[i][1])

arr.sort(key=lambda a: a[1])
values = [a[1] for a in arr]

for i in range(n):
    a = cum[i]
    b = cum[n - 1] - cum[i]
    diff = a - b

    if diff == 0:
        print("YES")
        return
    elif(diff % 2 != 0):
        break
    else:
        diff //= 2
    idx = find(values, abs(diff))

    if(idx != -1 and ((diff > 0 and arr[idx[0]][0] <= i) or (diff < 0 and arr[idx[1]][0] > i))):
        print("YES")
        return
print("NO")


from functools import reduce

def solve():
    sum_ = a[:]
    for i in range(1, n):
        sum_[i] += sum_[i - 1]
    if (sum_[n - 1] % 2):  return False
    half = int(sum_[n - 1] / 2)
    st = set([0])
    for i in range(n):
        if sum_[i] >= half and sum_[i] - half in st:
            return True
        st.add(a[i])

    sum_ = a[:]
    for i in range(n - 2, -1, -1):
        sum_[i] += sum_[i + 1]
    st = set([0])
    for i in range(n - 1, -1, -1):
        if sum_[i] >= half and sum_[i] - half in st:
            return True
        st.add(a[i])
    return False

while True:
    try:
        n = int(input())
    except:
        break
    a = [int(x) for x in input().split(' ')]
    print('YES' if solve() else "NO")
    


class Dick:
    def __init__(self):
        self.s = 0
        self.m = dict()
    def add(self, x):
        self.s += x
        if x in self.m:
            self.m[x] += 1
        else:
            self.m[x] = 1
    def rm(self, x):
        self.s -= x
        if self.m[x] > 1:
            self.m[x] -= 1
        else:
            self.m.pop(x)
    def shasei(self):
        return self.s
    def ininder(self, x):
        return x in self.m
def ok(a,n):
    w = sum(a)
    if w & 1:
        return 0
    f = Dick()
    s = Dick()
    for x in a:
        s.add(x)
    w //= 2
    for i in range(n):
        if s.ininder(w - f.shasei()) or f.ininder(w - s.shasei()):
            return 1
        f.add(a[i])
        s.rm(a[i])
    return 0

n = int(input())
a = list(map(int, input().split()))
print("YES" if ok(a,n) else "NO")


n = int(input())
a = list(map(int, input().split()))
e = set([0])
p = 0
s = sum(a)
if s % 2:
    st = False
else:
    st = True
if st:
    st = False
    for j in range(2):
        for i in a:
            p += i
            e.add(i)
            if p - s // 2 in e:
                st = True
                break
        e = set([0])
        p = 0
        a.reverse()
print('YES' if st else 'NO')


def divider(a):
    t = sum(a)
    d = []
    d.append(-t)
    for i in range(len(a)):
        t -= 2 * a[i]
        d.append(-t)
        if t == 0:
            return ("YES")
    for i in range(len(a)):
        s = 2 * a[i]
        j = binary(d, s)
        if j > i and j != -1:
            return ("YES")
        j = binary(d, -s)
        if i >= j and j != -1:
            return ("YES")
    return ("NO")


def binary(a, value):
    hi = len(a)
    lo = -1
    while (lo + 1 < hi):
        mi = (lo + hi) // 2
        if a[mi] == value:
            return mi
        if a[mi] < value:
            lo = mi
        else:
            hi = mi
    return -1


def __starting_point():
    n = input()
    a = [int(i) for i in input().split()]
    print(divider(a))

__starting_point()

def f(aa, s):
    d = {a: i for i, a in enumerate(aa)}
    for i, a in enumerate(aa):
        if s in d and i <= d[s]:
            return True
        s -= a
        if s <= 0:
            break
    return not s


n = int(input())
aa = list(map(int, input().split()))
s, res = sum(aa), False
if not s & 1 and n > 1:
    res = f(aa, s // 2)
    if not res:
        aa.reverse()
        res = f(aa, s // 2)
print(("NO", "YES")[res])

from itertools import *
n = int(input())
l = list(map(int, input().split()))
for j in range(0, 2):
	m = {}
	l = [0] + list(reversed(l))
	for i in range(len(l)):
		m[l[i]] = i
	ac = list(accumulate(l))
	s = ac[-1]
	for i in range(0, len(ac)-1):
		if ac[i] == s/2 or (s/2-ac[i] in m.keys() and m[s/2-ac[i]] > i):
			print('YES')
			quit()
print('NO')




def func():
    n = int(input())


    array = []
    sum = 0
    for index,number in enumerate(input().split()):
        num = int(number)
        array.append(num)
        sum += num

    if sum%1 ==1:
        print("NO")
        return
    setn = set()
    sumSub = 0
    indexdict = {}
    for indexm,number in enumerate(array):
        sumSub += number


        sum2 = sumSub * 2 - sum
        if sum2%2 == 1:
            continue
        sum2 /= 2
        setn.add(sum2)
        indexdict[sum2] = indexm

    i = 0
    if 0 in setn:
        print("YES")
        return
    while i < n:
        num = array[i]

        if num in setn and num in indexdict and i < indexdict[num]:

            print("YES")
            return
        if -num in setn and -num in indexdict and i > indexdict[-num]:
            print("YES")
            return
        i+=1

    print("NO")

func()


#!/usr/bin/env python3

import sys
from collections import Counter

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

s = sum(a)
c1 = Counter(a)
c2 = Counter()

cur = 0
for x in a:
    c1[x] -= 1
    c2[x] += 1
    cur += x

    s1 = cur
    s2 = s - s1
    if s1 == s2:
        print('YES')
        return
    if (s2 - s1) % 2 == 1:
        continue
    if s2 > s1:
        if c1[(s2 - s1) // 2] > 0:
            print('YES')
            return
    else:
        if c2[(s1 - s2) // 2] > 0:
            print('YES')
            return

print('NO')