有一次,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