← 返回题目列表

Codeforces · 21/C

C. 条纹 2

中文机器翻译题面 查看原题

有一次,Bob 拿了一条 n 格的纸条(条的高度是 1 格)。他在每个方格中写下了一个整数,可能是负数。他开始感兴趣的是,有多少种方法可以将该条纹切成三块,使得每块的数字之和等于任何其他块的数字之和,并且每块包含正整数数量的正方形。你能帮鲍勃解决这个问题吗?

输入

第一个输入行包含整数 n (1 ≤ n ≤ 105) — 条带中的方块数量。第二行包含 n 个空格分隔的数字——它们是写在条纹方块中的数字。这些数字是整数,绝对值不超过 10000。

输出

输出将条带切割成三个非空块的方式数量,使得每个块的数字之和等于任何其他块的数字之和。不要忘记只能沿着方块的边界切割条纹。

示例

输入 #1

4
1 2 3 3

输出 #1

1

输入 #2

5
1 2 3 4 5

输出 #2

0