1785: 神之天平

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：76 解决：29

题目描述

有n个调查员误入了金字塔，唤醒了其中的古老者，阿斯特赖雅将这n个调查员的灵魂排成一排，对他们进行审判。

阿斯特赖雅对这排灵魂进行若干次如下操作：

1.将最左边的灵魂放到左边的托盘上。

2.将最右边的灵魂放到右边的托盘上。

（每次操作可以只进行1或2，也可以1，2都进行）

只有当天平平衡时，天平上的灵魂才会被释放。请问一次最多有多少个调查员的灵魂可以被释放？

输入

第一行，一个正整数n，调查员的数量。  1 <= n <= 1e5

第二行，n个正整数，代表第i个调查员灵魂的重量。  1 <= 灵魂重量 <= 1e6;

输出

一行，一个正整数，被释放的调查员灵魂的最大数量

样例输入 复制 

9
7 3 20 5 15 1 11 8 10

样例输出 复制 

7

提示

提示：
灵魂重量之和可能会爆int


样例说明：
从左往右拿前三个和后四个，左边和右边重量均为30，此时释放的灵魂最多，为7个