题目内容

档案馆要把一份长度为 $n$ 的卷宗做均分裁切。第 $i$ 页的页码权重为 $a_i$。起初整份卷宗作为唯一一段 $[1,n]$ 放在待处理集合中。每次必须取出集合里一段长度严格大于 2 的完整段 $[l,r]$，再选切点 $mid$（$l < mid \le r$）：当且仅当 $\sum_{i=l}^{mid-1} a_i = \sum_{i=mid}^{r} a_i$ 时，才能把该段替换为 $[l,mid-1]$ 与 $[mid,r]$。被裁开的段立即离开集合，之后只能对当前集合中的完整段继续操作，不能跨段或在段内另取子区间。下标始终相对原卷宗。请在最优策略下求出最多能裁切多少次；一次都不能切则输出 0。

约束：页数不超过 1000000，每个页码权重为正整数且不超过 1000000000。

输入描述

第一行一个整数 $n$，表示卷宗页数。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各页权重。 保证 $1 \le n \le 1000000$，$1 \le a_i \le 1000000000$。

输出描述

输出一个整数，表示最多裁切次数。

样例1

输入

4
1 1 1 1

输出

1

说明

整段和为 4，可在前缀和为 2 处切断，得到两段长度均为 2 的段，无法再切，共 1 次。

样例2

输入

3
2 2 2

输出

0

说明

三段负荷均为 2，总和 6 为偶数，但前缀和中不存在等于半和 3 的位置，无法切断，答案为 0。

样例3

输入

7
2 2 4 1 1 2 4

输出

4

说明

先把整段按半和切开，左右子段仍可能继续均分。按唯一切点递归，总共可切 4 次。

样例4

输入

1
9

输出

0

说明

长度 1 无法切断，答案为 0。