给定一个长为n的数组a[1],a[2],...,a[n]。

现在你需要把该数组分为三份，也就是选择两个位置，将其断开。之后你得到三个子数组(可以为空，即一个元素也没有)。

假设你选择i,j两个位置(i<=j)将数组断开，那么三个子数组分别为:

1. a[1],a[2],...,a[i]

2. a[i+1],a[i+2],...,a[j]

3. a[j+1],a[j+2],...,a[n]

我们记三个子数组的所有元素和分别为sum1,sum2,sum3;

sum1=a[1]+a[2]+...+a[i]

sum2=a[i+1]+a[i+2]+...+a[j]

sum3=a[j+1]+a[j+2]+...+a[n]

注意：空数组的元素和为0。

小Y同学希望截断后的数组满足：

sum1=sum3且sum1尽可能大

请你计算sum1的最大可能值。

显然，上述问题一定有解。因为我们可以令i=0,j=n，于是sum1=sum3=0。

第一行一个整数n(n<=200000)，表示数组长度。

第二行n个整数a[1],a[2],...a[n]。a[i]<=1e9。