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], [~]$.
[{"code": "input()\nnum = list(map(int, input().split()))\nmaxn = 0\nl, r = 0, len(num)-1\nj1, j2 = num[l], num[r]\nwhile l < r:\n    if j1 == j2:\n        maxn = max(j1, maxn)\n        l += 1\n        j1 += num[l]\n    elif j1 < j2:\n        l += 1\n        j1 += num[l]\n    else:\n        r -= 1\n        j2 += num[r]\nprint(maxn)\n", "passed": true, "time": 1.9, "memory": 14268.0, "status": "done"}, {"code": "\ndef mi():\n\treturn map(int, input().split())\n\nn = int(input())\na = list(mi())\n\ni1 = 0\ni2 = n-1\n\ncand = []\n\ns1 = s2 = 0\ns1 += a[i1]\ns2 += a[i2]\nwhile i1<i2:\n\tif s1==s2:\n\t\tcand.append(s1)\n\t\ti1+=1\n\t\ti2-=1\n\t\tif i1==n or i2==-1:\n\t\t\tbreak\n\t\ts1 += a[i1]\n\t\ts2 += a[i2]\n\telif s1<s2:\n\t\ti1+=1\n\t\tif i1==n or i2==-1:\n\t\t\tbreak\n\t\ts1 += a[i1]\n\telse:\n\t\ti2-=1\n\t\tif i1==n or i2==-1:\n\t\t\tbreak\n\t\ts2 += a[i2]\nif len(cand):\n\tprint (cand[-1])\nelse:\n\tprint (0)", "passed": true, "time": 0.21, "memory": 14212.0, "status": "done"}, {"code": "length = int(input())\nnumbers = list(map(int, input().split(\" \")))\n\nmaxTotal = 0\ntotalLeft = 0\nindexLeft = 0\ntotalRight = 0\nindexRight = length - 1\n\nwhile indexLeft <= indexRight:\n    if totalLeft > totalRight:\n        totalRight += numbers[indexRight]\n        indexRight -= 1\n    else:\n        totalLeft += numbers[indexLeft]\n        indexLeft += 1\n    if totalRight == totalLeft:\n        maxTotal = max(maxTotal, totalLeft)\nprint(maxTotal)\n", "passed": true, "time": 0.24, "memory": 14296.0, "status": "done"}, {"code": "n = int(input())\n\nnumbers = [int(i) for i in input().split(\" \")]\n\ns = 0\na = 0\nsum1 = 0\nb = n - 1\nsum2 = 0\nwhile a <= b:\n    if sum1 < sum2:\n        sum1 += numbers[a]\n        a += 1\n    else:\n        sum2 += numbers[b]\n        b -= 1\n\n    if sum1 == sum2:\n        s = sum1\n\nprint(s)\n\n", "passed": true, "time": 0.16, "memory": 14124.0, "status": "done"}, {"code": "n = int(input())\nl = list(map(int,input().split()))\nl_sum = sum(l)\nc_sum = [0 for _ in range(n)]\ntotal = 0\n\nmid = None\nfor i, x in enumerate(l): \n    total += x\n    c_sum[i] = total\n    if mid is None and total >= l_sum//2:\n        mid = i\n\npoint_left = mid\npoint_right = mid + 1\nsum_left = c_sum[mid]\nsum_right = total-c_sum[mid]\n\nwhile sum_left != sum_right:\n    if point_left<0:break\n    if point_right>=n:break\n\n\n    if sum_left>sum_right:\n        sum_left -= l[point_left]\n        point_left -= 1\n    else:\n        sum_right -= l[point_right]\n        point_right += 1\n\n\nprint (min(sum_left,sum_right))", "passed": true, "time": 0.14, "memory": 14284.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\n\ns1, s3 = 0, 0\nmax_s = 0\nl, r = 0, n-1\nwhile l <= r:\n    if s1 > s3:\n        s3 += a[r]\n        r -= 1\n    else:\n        s1 += a[l]\n        l += 1\n\n    if s1 == s3:\n        max_s = s1\n\nprint(max_s)", "passed": true, "time": 0.15, "memory": 14200.0, "status": "done"}, {"code": "n=int(input())\nL=list(map(int,input().split()))\nsmax=0\ni=0\nj=n-1\nt1=0\nt3=0\nt1+=L[i]\nt3+=L[j]\nwhile(i<j):\n    if(t1==t3):\n        smax=max(smax,t1)\n        i+=1\n        t1+=L[i]\n    elif(t1>t3):\n        j-=1\n        t3+=L[j]\n    else:\n        i+=1\n        t1+=L[i]\nprint(smax)\n", "passed": true, "time": 0.15, "memory": 14240.0, "status": "done"}, {"code": "n = int(input())\nD = list(map(int, input().split()))\nsums1, sums2 = {}, {}\n\ns = 0\nfor i, d in enumerate(D):\n    s += d\n    if s not in sums1:\n        sums1[s] = i\n\ns = 0\nfor i, d in enumerate(D[::-1]):\n    s += d\n    if s not in sums2:\n        sums2[s] = i\n\nsums1 = sorted(list(sums1.items()), reverse=True)\nanswer = 0\nfor s, i in sums1:\n    if s in sums2 and sums2[s]+i+2 <= n:\n        answer = s\n        break\nprint(answer)\n", "passed": true, "time": 0.15, "memory": 14292.0, "status": "done"}, {"code": "n = int(input())\nls = [int(i) for i in input().split()]\n\nif n == 1:\n    print(0);return\n\nf1, f2 = 0, n - 1\n\nans = 0\nsum1, sum2 = ls[0], ls[n-1]\nif sum1 == sum2:\n    ans = sum1\n    f1 += 1\n    sum1 += ls[f1]\n\nwhile True:\n    while sum1 != sum2 and f1 + 1 < f2:\n        if sum1 < sum2:\n            f1 += 1\n            sum1 += ls[f1]\n        else:\n            f2 -= 1\n            sum2 += ls[f2]\n\n    if sum1 == sum2:\n        ans = sum1\n        if f1 + 1 >= f2:\n            break\n        f1 += 1\n        sum1 += ls[f1]\n    else:\n        break\n\nprint(ans)\n\n\n", "passed": true, "time": 0.24, "memory": 14272.0, "status": "done"}, {"code": "from itertools import accumulate\n\nn = int(input())\nd = list(map(int, input().split()))\n\nleft = list(accumulate([0] + d))\nright = list(accumulate([0] + d[::-1]))\n\nans = 0\ni, j = 0, 0\n\nwhile i + j <= n:\n    le, ri = left[i], right[j]\n\n    if le == ri:\n        ans = le\n        i += 1\n        j += 1\n\n    elif le < ri:\n        i += 1\n\n    elif le > ri:\n        j += 1\n\n    else:\n        return\n\nprint(ans)\n", "passed": true, "time": 0.15, "memory": 14176.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\nb = a[::-1]\nsa = [0] * n\nsb = [0] * n\nsa[0] = a[0]\nsb[0] = b[0]\nfor i in range(1, n):\n    sa[i] = sa[i - 1] + a[i]\n    sb[i] = sb[i - 1] + b[i]\ni, j = 1, 1\nrec = []\nwhile i + j <= n:\n    if sa[i - 1] == sb[j - 1]:\n        rec.append(sa[i - 1])\n        i += 1\n    elif sa[i - 1] < sb[j - 1]:\n        i += 1\n    else:\n        j += 1\n\nif len(rec) == 0:\n    print(0)\nelse:\n    print(max(rec))", "passed": true, "time": 1.05, "memory": 14284.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\n\nx = 0\ny = 0\nz = sum(a)\npos = -1\n\nfor i in range(n):\n    x += a[i]\n    z -= a[i]\n    if x >= z:\n        pos = i\n        break\n\nl, r = pos, pos + 1\n\nwhile True:\n    # print(l, r)\n    if x > z and l >= 0:\n        x -= a[l]\n        l -= 1\n    elif x < z and r < n:\n        z -= a[r]\n        r += 1\n    elif x == z:\n        print(x)\n        return\n    elif l < 0 or r >= n:\n        print(0)\n        return", "passed": true, "time": 0.15, "memory": 14408.0, "status": "done"}, {"code": "n = int(input())\na = [int(x) for x in input().split()]\n\nleft = 0\nright = n - 1\nleft_sum = 0\nright_sum = 0\nequal = 0\nwhile left <= right  and left < n and right >= 0 :\n    if left_sum > right_sum:\n        right_sum += a[right]\n        right -= 1\n    else:\n        left_sum += a[left]\n        left += 1\n    if left_sum == right_sum:\n        equal = left_sum\n\nprint(equal)\n\n", "passed": true, "time": 0.15, "memory": 14160.0, "status": "done"}, {"code": "#from math import ceil, log\n\nt = 1#int(input())\nfor test in range(t):\n    n = int(input())\n    arr = list(map(int, input().split()))\n    l = -1\n    h = n\n    curMax = 0\n    sum1 = 0\n    sum3 = 0\n    while l<h:\n    \tif sum1==sum3:\n    \t\tcurMax = max(curMax, sum1)\n    \t\tl+=1\n    \t\tsum1+=arr[l]\n    \telif sum1<sum3:\n    \t\tl+=1\n    \t\tsum1+=arr[l]\n    \telse:\n    \t\th-=1\n    \t\tsum3+=arr[h]\n    print(curMax)\n\n\n", "passed": true, "time": 0.16, "memory": 14308.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\ni = -1\nj = n\ns1, s2 = 0, 0\nans = 0\nwhile i < j:\n    if s1 == s2:\n        ans = max(ans, s1)\n    if s1 >= s2:\n        j -= 1\n        s2 += a[j]\n\n\n    else:\n        i += 1\n        s1 += a[i]\n\nprint(ans)", "passed": true, "time": 0.14, "memory": 14184.0, "status": "done"}, {"code": "n = int(input())\n\ndata = list(map(int,input().split()))\n\n\nind_l = 0\nind_r = n - 1\n\nsum_l = 0\nsum_r = 0\n\nanswer = 0\nwhile ind_l <= ind_r:\n    sum_l+=data[ind_l]\n    ind_l+=1\n\n    while (sum_l > sum_r) and ind_l <= ind_r:\n        sum_r += data[ind_r]\n        ind_r -= 1\n\n    \n    if (sum_l == sum_r):\n        answer = sum_l\n\nprint(answer)\n", "passed": true, "time": 0.16, "memory": 14064.0, "status": "done"}, {"code": "R = lambda: map(int, input().split())\n\nn = int(input())\na = list(R())\n\nans = 0\ni = 0\nj = n - 1\ns1 = 0\ns3 = 0\n\nwhile i < j:\n    if s1 + a[i] == s3 + a[j]:\n        s1 += a[i]\n        s3 += a[j]\n        i += 1\n        j -= 1\n        ans = s1\n    elif s1 + a[i] < s3 + a[j]:\n        s1 += a[i]\n        i += 1\n    else:\n        s3 += a[j]\n        j -= 1\nprint(ans)", "passed": true, "time": 0.15, "memory": 14272.0, "status": "done"}, {"code": "n = int(input())\nl = list(map(int, input().split()))\n\nmx = 0\nleft = 0\nright = n - 1\nsl = 0\nsr = 0\nwhile left <= right:\n\tif sl == sr:\n\t\tmx = sl\n\t\tsl += l[left]\n\t\tleft += 1\n\telif sl > sr:\n\t\tsr += l[right]\n\t\tright -= 1\n\telif sl < sr:\n\t\tsl += l[left]\n\t\tleft += 1\nif sl == sr:\n\tmx = sl\nprint(mx)", "passed": true, "time": 0.14, "memory": 14144.0, "status": "done"}, {"code": "n = int(input())\na = [int(i) for i in input().split()]\ni = -1\nj = n\nsum1 = 0\nsum2 = 0\nans = 0\nwhile i < j:\n    while (sum1 <= sum2) and (i < j):\n        i += 1\n        if i == j:\n            break\n        sum1 += a[i]\n        if (sum1 == sum2) and (sum1 > ans):\n            ans = sum1\n#    print(i, j, sum1, sum2)\n    while (sum2 <= sum1) and (j > i):\n        j -= 1\n        if i == j:\n            break\n        sum2 += a[j]\n        if (sum1 == sum2) and (sum1 > ans):\n            ans = sum1\n#    print(i, j, sum1, sum2)\n\nprint(ans)\n\n", "passed": true, "time": 0.14, "memory": 14292.0, "status": "done"}, {"code": "import bisect\n\nn = int(input())\na = list(map(int, input().split(' ')))\n\nprefs = [a[0]] * n\nsuffs = [a[n - 1]] * n\nfor i in range(1, len(a)):\n\tprefs[i] = prefs[i - 1] + a[i]\nfor i in reversed(list(range(0, len(a) - 1))):\n\tsuffs[i] = suffs[i + 1] + a[i]\n\nans = 0\nfor i in range(len(a)):\n\ts = suffs[i]\n\tind = bisect.bisect_left(prefs, s)\n\tif prefs[ind] == s and ind < i:\n\t\tans = s\n\t\tbreak\n\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14200.0, "status": "done"}, {"code": "n=int(input())\na=list(map(int,input().split()))\nsuma=i=0\nflag=0\nsum1=0\nsum3=0\nj=n-1\nidxs=i\nidxe=j\nwhile(True):\n    if((sum1==0 and sum3==0) or (sum1<sum3)):\n        sum1+=a[i]\n        i+=1\n    elif(sum3<sum1):\n        sum3+=a[j]\n        j-=1\n    elif(sum1==sum3):\n        suma+=sum1\n        flag=1\n        sum1=0\n        sum3=0\n    if(j<i-1):\n        break\n    \n\nif(flag):\n    print(suma)\nelse:\n    print(0)\n", "passed": true, "time": 0.14, "memory": 14272.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n\nn = int(input())\nx = [int(i) for i in input().split()]\n\nS1, S3, L, R = 0, 0, -1, n\nMaxS = 0\nwhile L < R:\n    if S1 == S3:\n        MaxS = S1\n        L += 1\n        S1 += x[L]\n    elif S1 > S3:\n        R -= 1\n        S3 += x[R]\n    else:\n        L += 1\n        S1 += x[L]\nprint(MaxS)\n\n\n", "passed": true, "time": 0.16, "memory": 14052.0, "status": "done"}, {"code": "length = int(input())\n\nnumbers = list(map(int, input().split(' ')))\n\nlastResult = 0\n\nsum1, sum3 = 0, 0\ni1, i3 = 0, length-1\n\nwhile True:\n    if i1 > i3:\n        break\n    if sum1 < sum3:\n        sum1 += numbers[i1]\n        i1 += 1\n    elif sum1 > sum3:\n        sum3 += numbers[i3]\n        i3 -= 1\n    else:\n        lastResult = sum1\n        sum1 += numbers[i1]\n        i1 += 1\n\nprint(sum1 if sum1 == sum3 else lastResult)", "passed": true, "time": 0.15, "memory": 14244.0, "status": "done"}, {"code": "n = int(input())\na = list(map(int, input().split()))\ni, j, si, sj, r = -1, len(a), 0, 0, 0\nwhile i <  j:\n    if si == sj: r = si\n    if si < sj:\n        i += 1\n        si += a[i]\n    else:\n        j -= 1\n        sj += a[j]\nprint( r )\n", "passed": true, "time": 0.14, "memory": 14296.0, "status": "done"}]