Problem2673--一分为二

2673: 一分为二

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 41  Solved: 15
[Status] [Submit] [Creator:]

Description



给定一个长度为 n(2  n  106) 的数列 a1, a2, ..., an(-109  ai  109)。

你需要将这个数列切割成两段,要求每一段至少包含一个数列元素,同时这两段对应的元素和相同。

换句话说,你需要确定一个下标 p(1 p < n),满足:  



 a1 + a2 +... + ap = ap+1 + ap+2 + ... + an



问:存在多少种合法的划分方案?

即判断存在多少个下标 p 满足 1 p < n 且 a1 + a2 + ... + ap = ap+1 + ap+2 + ... + a。  


Input

第一行,一个整数 n(2 n 106)。  

第二行,n 个整数 a1, a2, ..., an(-109 ai 109),两两之间以一个空格分隔。  

Output

输出一个整数,表示满足题目要求的划分方案。

Sample Input Copy

8
1 -3 4 -1 -2 3 -1 3

Sample Output Copy

2

HINT

  • 对于 30% 的数据,n 100, |ai| 103
  • 对于 60% 的数据,n 104, |ai| 106
  • 对于 100% 的数据,2  n  106, |ai|  109

Source/Category