题目描述

有一天，小S拿出了一张有着 n 个方格的长纸条，纸条的高度是一个方格。在每个方格中，他写下了一个整数（有可能为负数）。他开始对有多少种方法将这个纸条切割成两部分，使得一部分的数字之和等于另一部分数字之和，并且每块都只能包含正整数数量的方格。你能帮助小S解决这个问题吗？

输入描述

第一行一个正整数 n，代表纸条内的方格数量。

第二行包含 n 个空格分隔的整数数字。

输出描述

将纸条切割成两个非空纸条，使得一部分的数字之和等于另一部分数字之和的方案数。

注意，只允许沿着方格的边界切割纸条。

样例描述

9
1 5 -6 7 9 -16 0 -2 2

3

存在三种切法：

• {1,5,-6} {7,9,-16,0,-2,2}
• {1,5,-6,7,9,-16} {0,-2,2}
• {1,5,-6,7,9,-16,0} {-2,2}

3
1 1 1

0

2
0 0

1

数据范围描述

对于 $40\%$ 的数据保证，$n\leq1000$。

对于 $100\%$ 的数据保证，$n\leq10^6$，$-1000\leq a_i \leq 1000$。

来源 2023青岛市市北区区赛初中组 T1