曾经，Bob拿了一条有n个方块的纸条（纸条的高度为1个方块）。他在每个方块上写了一个整数，可能是负数。他对如何将这条纸条切成两段感兴趣，使得一段的数字之和等于另一段的数字之和，并且每一段都包含正整数个方块。你能帮帮Bob解决这个问题吗？

输入

第一行输入一个整数n（**1 ≤ n ≤ 10^5）— 纸条上的方块数。第二行输入n个用空格分隔的数字 — 它们是写在纸条方块上的数字。这些数字是整数，绝对值不超过10000。

输出

输出将纸条切成两个非空段的方式数量，使得一段的数字之和等于另一段的数字之和。不要忘记只能沿着方块的边界切割纸条。

Samples

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

3

3
1 1 1

0

2
0 0

1