解题思路

先设前缀和数组为 $pre$，其中

并约定 $pre[0]=0$。

题目内容

给定一个长度为 $n$ 的数组 {$a_1，a_2,...,a_n$}。你将对数组进行若干次“切割”操作，操作规则如下：

• 一开始，数组段集合仅包含整段 $[1,n]$ ;

• 每次操作，必须从“当前数组段集合”中选择一段完整的数组段 $[l,r]$ (该段长度需严格大于 $2$ )，然后选择一个位置 $mid(l<mid≤r)$，若满足：

$\sum_{i=l}^{m i d-1} a_{i}=\sum_{i=m i d}^{r} a_{i}$

则可以把该数组段分成两段 $[l,mid-1]$ 与 $[mid,r]$，并以这两段替换原来的 $[l,r]$，继续加入到数组段集合中;

• 一旦一个数组段被切割，它将从集合中移除并被两个新的子段取代。你只能选择当前集合中存在的完整段进行下一次切割，不允许跨越段边界或在段内截取任意子段进行操作。

所有区间均以原数组的下标表示，不进行重新编号;切割后得到的两个区间互不重叠，且并集为原区间。请你计算，在最优策略下，总共最多能进行多少次切割。

输入描述

第一行输入个整数 $n(1≤n≤10^6)$ 表示数组的长度

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n (1≤a_i≤10^9)$ 表示数组中的元素。

输出描述

输出一个整数，表示最多的切割次数，若不存在任何合法的切割方案，输出 $0$ 。

样例1

输入

6
1 2 1 1 1 2

输出

2

说明

对全段 $[1,6]$ ，可在 $mid=4$ 处切割，因为 $1+2+1=1+1+2$ 。得到 $[1,3]$ 与 $[4,6]$ 。随后 $[4,6]$ 在 $mid=6$ 处再次切割，因为 $1+1=2$ 。总共进行了 $2$ 次切割。