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
# url: https://codeforces.com/contest/1006/problem/C

from sys import stdin, stdout
input = stdin.readline
print = stdout.write

def main():
    # test cases
    tc = 1 # int(input())
    # read bulk input
    all_input = stdin.readlines()
    # current position of input reader
    reader = 0

    def get_input_parameters(reader: int):
        n = int(all_input[reader])
        reader += 1
        d = list(map(int, all_input[reader].strip().split()))
        reader += 1
        return (n, d, reader)

    '''
    Same problem was rephrased and given as 1669F
    '''    
    def solve(n: int, d: list[int]):
        ans = 0
        left, right = 0, n - 1
        sumLeft, sumRight = d[left], d[right]
        while left != right:
            # if the sums are equal
            if sumLeft == sumRight:
                # update answer
                ans = sumLeft
                # move the pointer
                left += 1
                if left == right: break
                sumLeft += d[left]
            
            # else, move the pointers till they are unequal
            while sumLeft < sumRight and left != right:
                left += 1
                sumLeft += d[left]
            while sumRight < sumLeft and right != left:
                right -= 1
                sumRight += d[right]
        
        return ans

    # bulk output
    all_output = ['']*tc
    # fill the output
    def fill_output(x: int, index: int) -> None:
        all_output[index] = str(x)

    # the executor
    for index in range(tc):
        n, d, reader = get_input_parameters(reader)
        ans = solve(n, d)
        fill_output(ans, index)
    
    # print the final answer
    print('\n'.join(all_output))

if __name__ == main(): main()
		  			  		  	 	   	 	 	 				 	