You are given an array

${\mathrm{d1,d2,\dots ,dnd1,d2,\dots ,dn\; consisting\; of\; nn\; 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 $\mathrm{sum1sum1\; ,\; the\; sum\; of\; elements\; of\; the\; second\; part\; be\; sum2sum2\; and\; the\; sum\; of\; elements\; of\; the\; third\; part\; be\; sum3sum3\; .\; Among\; all\; possible\; ways\; to\; split\; the\; array\; you\; have\; to\; choose\; a\; way\; such\; that\; sum1=sum3sum1=sum3\; and\; sum1sum1\; is\; maximum\; possible.}$

More formally, if the first part of the array contains $\mathrm{aa\; elements,\; the\; second\; part\; of\; the\; array\; contains\; bb\; elements\; and\; the\; third\; part\; contains\; cc\; elements,\; then:}$

$$\mathrm{sum1=\sum 1\le i\le adi,sum1=\sum 1\le i\le adi,\; sum2=\sum a+1\le i\le a+bdi,sum2=\sum a+1\le i\le a+bdi,\; sum3=\sum a+b+1\le i\le a+b+cdi.sum3=\sum a+b+1\le i\le a+b+cdi.}$$

The sum of an empty array is $\mathrm{00\; .}$

Your task is to find a way to split the array such that $\mathrm{sum1=sum3sum1=sum3\; and\; sum1sum1\; is\; maximum\; possible.}$

Input

The first line of the input contains one integer $\mathrm{nn\; (1\le n\le 2\cdot 1051\le n\le 2\cdot 105\; )\; —\; the\; number\; of\; elements\; in\; the\; array\; dd\; .}$

The second line of the input contains $\mathrm{nn\; integers\; d1,d2,\dots ,dnd1,d2,\dots ,dn\; (1\le di\le 1091\le di\le 109\; )\; —\; the\; elements\; of\; the\; array\; dd\; .}$

Output

Print a single integer — the maximum possible value of $\mathrm{sum1sum1\; ,\; considering\; that\; the\; condition\; sum1=sum3sum1=sum3\; must\; be\; met.}$

Obviously, at least one valid way to split the array exists (use $\mathrm{a=c=0a=c=0\; and\; b=nb=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 $\mathrm{sum1sum1\; :\; [1,3,1],[ ],[1,4][1,3,1],[ ],[1,4]\; .}$

In the second example the only way to have $\mathrm{sum1=4sum1=4\; is:\; [1,3],[2,1],[4][1,3],[2,1],[4]\; .}$

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

$题意：将长度为n的集合划分为3个集合要求sum1==sum3,并且求出在满足条件的基础上sum1的最大值，sum1，sum2均可为空集。$

$分析：我们可以sum1从前往后加，sum3从后往前加，从满足条件(sum1==sum3)中取最大值就OK。$

1 #include 
          
            2 #include 
           
             3 #include
            
              4 #include
             
               5 #include