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.
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$.
5
1 3 1 1 4
5
5
1 3 2 1 4
4
3
4 1 2
0
1
1000000000
0
2
1 1
1
5
1 3 5 4 5
9
# main >>> Version 16.0
def main() -> None:

    # 2023-07-08 00:03:57 Rating 1200
    def prefixSum(arr:list) -> list:
        newArray,idx = [],0
        while idx < len(arr):
            if idx==0: newArray.append(arr[idx])
            else: ans = arr[idx] + newArray[-1]; newArray.append(ans)
            idx+=1
        return newArray

    def binary_search_function(input_list:list, low_value:int, high_value:int,  target_value:int) -> None:
        if high_value >= low_value:
            middle = (high_value + low_value) // 2
            if input_list[middle] < target_value: return binary_search_function(input_list, middle +1, high_value, target_value)
            elif input_list[middle] > target_value: return binary_search_function(input_list, low_value, middle-1, target_value)
            else: return middle
        else: return [high_value,low_value]

    length = ii()
    l = li()
    forward = prefixSum(l)
    backward = prefixSum(l[::-1])
    # just split into three parts and prefix sum forwards and backwards

    high = 0
    flag = False
    for idx,f in enumerate(forward):
        if idx < (length//2)+1:
            res = binary_search_function(backward, 0,length-1, f)
            if type(res)==int: high = res; flag = True
            else: pass
    p(backward[high]) if flag else p(0)
    
            
if __name__ == "__main__":
    import os, sys, math, itertools, bisect; from collections import deque, defaultdict, OrderedDict, Counter
    ii,si = lambda : int(input()), lambda : input()               
    mi, msi  = lambda : map(int,input().strip().split(" ")), lambda : map(str,input().strip().split(" ")) 
    li, lsi = lambda : list(mi()), lambda : list(msi())
    out, export, p, pp = [], lambda : print('\n'.join(map(str, out))), lambda x : out.append(x), lambda array : p(' '.join(map(str,array)))
    try: exec('from hq import L, LT, see, info, cmdIO, _generator_ \nline = [cmdIO(), main(), export(), _generator_()] \nfor l in line: l')
    except (FileNotFoundError,ModuleNotFoundError): main(); export()