You are given an array $d_1, d_2, \dots, d_n$ consisting of $n$ integer numbers.

Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array. 

Let the sum of elements of the first part be $sum_1$, the sum of elements of the second part be $sum_2$ and the sum of elements of the third part be $sum_3$. Among all possible ways to split the array you have to choose a way such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.

More formally, if the first part of the array contains $a$ elements, the second part of the array contains $b$ elements and the third part contains $c$ elements, then:

$$sum_1 = \sum\limits_{1 \le i \le a}d_i,$$ $$sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i,$$ $$sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.$$

The sum of an empty array is $0$.

Your task is to find a way to split the array such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the array $d$.

The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$) — the elements of the array $d$.


-----Output-----

Print a single integer — the maximum possible value of $sum_1$, considering that the condition $sum_1 = sum_3$ must be met.

Obviously, at least one valid way to split the array exists (use $a=c=0$ and $b=n$).


-----Examples-----
Input
5
1 3 1 1 4

Output
5

Input
5
1 3 2 1 4

Output
4

Input
3
4 1 2

Output
0



-----Note-----

In the first example there is only one possible splitting which maximizes $sum_1$: $[1, 3, 1], [~], [1, 4]$.

In the second example the only way to have $sum_1=4$ is: $[1, 3], [2, 1], [4]$.

In the third example there is only one way to split the array: $[~], [4, 1, 2], [~]$.

Difficulty: introductory

Starter code:

Solutions:
input()
num = list(map(int, input().split()))
maxn = 0
l, r = 0, len(num)-1
j1, j2 = num[l], num[r]
while l < r:
    if j1 == j2:
        maxn = max(j1, maxn)
        l += 1
        j1 += num[l]
    elif j1 < j2:
        l += 1
        j1 += num[l]
    else:
        r -= 1
        j2 += num[r]
print(maxn)



def mi():
	return map(int, input().split())

n = int(input())
a = list(mi())

i1 = 0
i2 = n-1

cand = []

s1 = s2 = 0
s1 += a[i1]
s2 += a[i2]
while i1<i2:
	if s1==s2:
		cand.append(s1)
		i1+=1
		i2-=1
		if i1==n or i2==-1:
			break
		s1 += a[i1]
		s2 += a[i2]
	elif s1<s2:
		i1+=1
		if i1==n or i2==-1:
			break
		s1 += a[i1]
	else:
		i2-=1
		if i1==n or i2==-1:
			break
		s2 += a[i2]
if len(cand):
	print (cand[-1])
else:
	print (0)

length = int(input())
numbers = list(map(int, input().split(" ")))

maxTotal = 0
totalLeft = 0
indexLeft = 0
totalRight = 0
indexRight = length - 1

while indexLeft <= indexRight:
    if totalLeft > totalRight:
        totalRight += numbers[indexRight]
        indexRight -= 1
    else:
        totalLeft += numbers[indexLeft]
        indexLeft += 1
    if totalRight == totalLeft:
        maxTotal = max(maxTotal, totalLeft)
print(maxTotal)


n = int(input())

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

s = 0
a = 0
sum1 = 0
b = n - 1
sum2 = 0
while a <= b:
    if sum1 < sum2:
        sum1 += numbers[a]
        a += 1
    else:
        sum2 += numbers[b]
        b -= 1

    if sum1 == sum2:
        s = sum1

print(s)



n = int(input())
l = list(map(int,input().split()))
l_sum = sum(l)
c_sum = [0 for _ in range(n)]
total = 0

mid = None
for i, x in enumerate(l): 
    total += x
    c_sum[i] = total
    if mid is None and total >= l_sum//2:
        mid = i

point_left = mid
point_right = mid + 1
sum_left = c_sum[mid]
sum_right = total-c_sum[mid]

while sum_left != sum_right:
    if point_left<0:break
    if point_right>=n:break


    if sum_left>sum_right:
        sum_left -= l[point_left]
        point_left -= 1
    else:
        sum_right -= l[point_right]
        point_right += 1


print (min(sum_left,sum_right))

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

s1, s3 = 0, 0
max_s = 0
l, r = 0, n-1
while l <= r:
    if s1 > s3:
        s3 += a[r]
        r -= 1
    else:
        s1 += a[l]
        l += 1

    if s1 == s3:
        max_s = s1

print(max_s)

n=int(input())
L=list(map(int,input().split()))
smax=0
i=0
j=n-1
t1=0
t3=0
t1+=L[i]
t3+=L[j]
while(i<j):
    if(t1==t3):
        smax=max(smax,t1)
        i+=1
        t1+=L[i]
    elif(t1>t3):
        j-=1
        t3+=L[j]
    else:
        i+=1
        t1+=L[i]
print(smax)


n = int(input())
D = list(map(int, input().split()))
sums1, sums2 = {}, {}

s = 0
for i, d in enumerate(D):
    s += d
    if s not in sums1:
        sums1[s] = i

s = 0
for i, d in enumerate(D[::-1]):
    s += d
    if s not in sums2:
        sums2[s] = i

sums1 = sorted(list(sums1.items()), reverse=True)
answer = 0
for s, i in sums1:
    if s in sums2 and sums2[s]+i+2 <= n:
        answer = s
        break
print(answer)


n = int(input())
ls = [int(i) for i in input().split()]

if n == 1:
    print(0);return

f1, f2 = 0, n - 1

ans = 0
sum1, sum2 = ls[0], ls[n-1]
if sum1 == sum2:
    ans = sum1
    f1 += 1
    sum1 += ls[f1]

while True:
    while sum1 != sum2 and f1 + 1 < f2:
        if sum1 < sum2:
            f1 += 1
            sum1 += ls[f1]
        else:
            f2 -= 1
            sum2 += ls[f2]

    if sum1 == sum2:
        ans = sum1
        if f1 + 1 >= f2:
            break
        f1 += 1
        sum1 += ls[f1]
    else:
        break

print(ans)




from itertools import accumulate

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

left = list(accumulate([0] + d))
right = list(accumulate([0] + d[::-1]))

ans = 0
i, j = 0, 0

while i + j <= n:
    le, ri = left[i], right[j]

    if le == ri:
        ans = le
        i += 1
        j += 1

    elif le < ri:
        i += 1

    elif le > ri:
        j += 1

    else:
        return

print(ans)


n = int(input())
a = list(map(int, input().split()))
b = a[::-1]
sa = [0] * n
sb = [0] * n
sa[0] = a[0]
sb[0] = b[0]
for i in range(1, n):
    sa[i] = sa[i - 1] + a[i]
    sb[i] = sb[i - 1] + b[i]
i, j = 1, 1
rec = []
while i + j <= n:
    if sa[i - 1] == sb[j - 1]:
        rec.append(sa[i - 1])
        i += 1
    elif sa[i - 1] < sb[j - 1]:
        i += 1
    else:
        j += 1

if len(rec) == 0:
    print(0)
else:
    print(max(rec))

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

x = 0
y = 0
z = sum(a)
pos = -1

for i in range(n):
    x += a[i]
    z -= a[i]
    if x >= z:
        pos = i
        break

l, r = pos, pos + 1

while True:
    # print(l, r)
    if x > z and l >= 0:
        x -= a[l]
        l -= 1
    elif x < z and r < n:
        z -= a[r]
        r += 1
    elif x == z:
        print(x)
        return
    elif l < 0 or r >= n:
        print(0)
        return

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

left = 0
right = n - 1
left_sum = 0
right_sum = 0
equal = 0
while left <= right  and left < n and right >= 0 :
    if left_sum > right_sum:
        right_sum += a[right]
        right -= 1
    else:
        left_sum += a[left]
        left += 1
    if left_sum == right_sum:
        equal = left_sum

print(equal)



#from math import ceil, log

t = 1#int(input())
for test in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    l = -1
    h = n
    curMax = 0
    sum1 = 0
    sum3 = 0
    while l<h:
    	if sum1==sum3:
    		curMax = max(curMax, sum1)
    		l+=1
    		sum1+=arr[l]
    	elif sum1<sum3:
    		l+=1
    		sum1+=arr[l]
    	else:
    		h-=1
    		sum3+=arr[h]
    print(curMax)




n = int(input())
a = list(map(int, input().split()))
i = -1
j = n
s1, s2 = 0, 0
ans = 0
while i < j:
    if s1 == s2:
        ans = max(ans, s1)
    if s1 >= s2:
        j -= 1
        s2 += a[j]


    else:
        i += 1
        s1 += a[i]

print(ans)

n = int(input())

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


ind_l = 0
ind_r = n - 1

sum_l = 0
sum_r = 0

answer = 0
while ind_l <= ind_r:
    sum_l+=data[ind_l]
    ind_l+=1

    while (sum_l > sum_r) and ind_l <= ind_r:
        sum_r += data[ind_r]
        ind_r -= 1

    
    if (sum_l == sum_r):
        answer = sum_l

print(answer)


R = lambda: map(int, input().split())

n = int(input())
a = list(R())

ans = 0
i = 0
j = n - 1
s1 = 0
s3 = 0

while i < j:
    if s1 + a[i] == s3 + a[j]:
        s1 += a[i]
        s3 += a[j]
        i += 1
        j -= 1
        ans = s1
    elif s1 + a[i] < s3 + a[j]:
        s1 += a[i]
        i += 1
    else:
        s3 += a[j]
        j -= 1
print(ans)

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

mx = 0
left = 0
right = n - 1
sl = 0
sr = 0
while left <= right:
	if sl == sr:
		mx = sl
		sl += l[left]
		left += 1
	elif sl > sr:
		sr += l[right]
		right -= 1
	elif sl < sr:
		sl += l[left]
		left += 1
if sl == sr:
	mx = sl
print(mx)

n = int(input())
a = [int(i) for i in input().split()]
i = -1
j = n
sum1 = 0
sum2 = 0
ans = 0
while i < j:
    while (sum1 <= sum2) and (i < j):
        i += 1
        if i == j:
            break
        sum1 += a[i]
        if (sum1 == sum2) and (sum1 > ans):
            ans = sum1
#    print(i, j, sum1, sum2)
    while (sum2 <= sum1) and (j > i):
        j -= 1
        if i == j:
            break
        sum2 += a[j]
        if (sum1 == sum2) and (sum1 > ans):
            ans = sum1
#    print(i, j, sum1, sum2)

print(ans)



import bisect

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

prefs = [a[0]] * n
suffs = [a[n - 1]] * n
for i in range(1, len(a)):
	prefs[i] = prefs[i - 1] + a[i]
for i in reversed(list(range(0, len(a) - 1))):
	suffs[i] = suffs[i + 1] + a[i]

ans = 0
for i in range(len(a)):
	s = suffs[i]
	ind = bisect.bisect_left(prefs, s)
	if prefs[ind] == s and ind < i:
		ans = s
		break

print(ans)


n=int(input())
a=list(map(int,input().split()))
suma=i=0
flag=0
sum1=0
sum3=0
j=n-1
idxs=i
idxe=j
while(True):
    if((sum1==0 and sum3==0) or (sum1<sum3)):
        sum1+=a[i]
        i+=1
    elif(sum3<sum1):
        sum3+=a[j]
        j-=1
    elif(sum1==sum3):
        suma+=sum1
        flag=1
        sum1=0
        sum3=0
    if(j<i-1):
        break
    

if(flag):
    print(suma)
else:
    print(0)


#!/usr/bin/env python3

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

S1, S3, L, R = 0, 0, -1, n
MaxS = 0
while L < R:
    if S1 == S3:
        MaxS = S1
        L += 1
        S1 += x[L]
    elif S1 > S3:
        R -= 1
        S3 += x[R]
    else:
        L += 1
        S1 += x[L]
print(MaxS)




length = int(input())

numbers = list(map(int, input().split(' ')))

lastResult = 0

sum1, sum3 = 0, 0
i1, i3 = 0, length-1

while True:
    if i1 > i3:
        break
    if sum1 < sum3:
        sum1 += numbers[i1]
        i1 += 1
    elif sum1 > sum3:
        sum3 += numbers[i3]
        i3 -= 1
    else:
        lastResult = sum1
        sum1 += numbers[i1]
        i1 += 1

print(sum1 if sum1 == sum3 else lastResult)

n = int(input())
a = list(map(int, input().split()))
i, j, si, sj, r = -1, len(a), 0, 0, 0
while i <  j:
    if si == sj: r = si
    if si < sj:
        i += 1
        si += a[i]
    else:
        j -= 1
        sj += a[j]
print( r )