小小潘有一个长度为n的整数数组{d1,d2,…,dn}。

小曹老师希望它将这个数组分成3部分，可以为空，即某一部分没有元素，并保证每一个数都被分配过，每一部分元素的下标都必须连续的。

假设三部分的和分别为sum1, sum2,sum3。 小小潘需要在所有方案中找到一个方案使得sum1=sum3且sum1尽可能的大。

再解释下三个sum，如果第一部分包含a个整数，第二部分包含b个整数而第三部分包含c个，那么：

如果某一部分使空的，那么它的和为0。

第一行一个整数n (1≤n≤2*10^5)

第二行包含n个整数d1,d2,…,dn(0≤di≤10^9)

输出一个整数, sum1的最大值

样例：[1,3,1],[ ],[1,4]