小明在越南旅游，参加了当地的娱乐活动。小明运气很好，拿到了大奖， 到了最后的拿奖金环节。小明发现桌子上放着一列红包，每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”2刀，将这一列红包“切”成3组，并且第一组的奖金之和等于最后一组奖金和（允许任意一组的红包集合是空）。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少，你能帮他算算吗。
举例解释：桌子上放了红包 1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀，将红包分成3组 [1, 2, 3, 4] [7] [10]，其中第一组奖金之和=第三组奖金之和=10，所以小明可以拿到10越南盾。
输入描述:
第一行包含一个正整数n，(1<=n<= 200 000)，表示有多少个红包。
第二行包含n个正整数d[i]，表示每个红包包含的奖金数额。其中1<= d[i] <= 1000 000 000
输出描述:小明可以拿到的总奖金
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int data[200005];
int i = 0;
while (i<n)
{
cin>>data[i++];
}
long long lsum = data[0];
long long rsum = data[n-1];
int j = n-1;
i = 0;
//cout<<n<<" j:"<<j<<endl;
long long tmp = 0;
while(i < j){
if(lsum < rsum){
i++;
lsum += data[i];
}else if (rsum < lsum){
j--;
rsum += data[j];
}else{
tmp = lsum;
if(j-i<=1) break;
i++;
lsum += data[i];
j--;
rsum += data[j];
}
}
cout<<(lsum == rsum ? lsum: tmp)<<endl;
getchar();
cin>>n;
}
