Codeforces Round #498 (Div. 3) C. Three Parts of the Array

题目链接： http://codeforces.com/contest/1006/problem/C

C. Three Parts of the Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 $su{m}_1$, the sum of elements of the second part be $su{m}_2$ and the sum of elements of the third part be $su{m}_3$. Among all possible ways to split the array you have to choose a way such that $su{m}_1=su{m}_3$ and $su{m}_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:

$$su{m}_1=\sum _{1\le i\le a}{d}_i,$$$$su{m}_2=\sum _{a+1\le i\le a+b}{d}_i,$$$$su{m}_3=\sum _{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 $su{m}_1=su{m}_3$ and $su{m}_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 $su{m}_1$, considering that the condition $su{m}_1=su{m}_3$ must be met.

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

Examples

input

Copy

5
1 3 1 1 4

output

Copy

5

input

Copy

5
1 3 2 1 4

output

Copy

4

input

Copy

3
4 1 2

output

Copy

0

Note

In the first example there is only one possible splitting which maximizes $su{m}_1$: $[1,3,1],\left[\right],[1,4]$.

In the second example the only way to have $su{m}_1=4$ is: $[1,3],[2,1],\left[4\right]$.

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

题意：给你n个数，相对顺序不能变，把他分为3个区域，每个区域和分别为sum1,sum2,sum3,区域可以为空，条件：需要sum1==sum3。问你最大的sum1和sum3是多少？

题解：因为分数字的时候相对位置不能变，所以直接两边往中间靠近就可以了。

 

#include<stdio.h>
int main()
{
    int n;
    long long number[200010];
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    {
        scanf("%lld",&number[i]);
    }
    long long sum1=0;long long sum3=0;long long max=0;
    int l=0,r=n-1;
    while(l<=r)
    {
        if(sum1<sum3)
        {
            sum1+=number[l];
            l++;
        }
        if(sum1>sum3)
        {
            sum3+=number[r];
            r--;
        }
        if(sum1==sum3)
        {
            if(sum1>max)
            max=sum1;
            sum1+=number[l];
            l++;
        }
    }
    printf("%lld\n",max);
}