#1046. Stripe2

Stripe2

问题描述(翻译)

有一次鲍勃拿了一条n个正方形的纸条(条纹的高度是1个正方形)。在每个方格中,他写了一个整数,可能是负数。他开始对有多少种方法将这条条纹切成两部分感兴趣,以便一块的数字之和等于另一块的数字之和,两块正方形数量不为空,且每块至少包含一个含有正整数数字的正方形。你会帮助鲍勃解决这个问题吗?

第一行包含整数 n 1 ≤ n ≤ 105) — 条带中的正方形数量。第二行包含 n 个空格分隔的数字 — 它们是用纸条的正方形中书写的数字。这些数字是整数,绝对值不超过 10000。

输出将条带切割成两个非空段的方法数量,以便一段的数字之和等于另一段的数字之和。不要忘记,它只允许沿着正方形的边界切割条纹。 输出将条带切割成两个非空段的方法数量,以便一段的数字之和等于另一段的数字之和。不要忘记,它只允许沿着正方形的边界切割纸条。

输入

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

输出

将条带切割成两个非空段的方法数量,以便一段的数字之和等于另一段的数字之和。不要忘记,它只允许沿着正方形的边界切割纸条。

题目原文

Once Bob took a paper stripe of n squares (the height of the stripe is 1 square). In each square he wrote an integer number, possibly negative. He became interested in how many ways exist to cut this stripe into two pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece, and each piece contains positive integer amount of squares. Would you help Bob solve this problem?

The first input line contains integer n (1 ≤ n ≤ 105) — amount of squares in the stripe. The second line contains n space-separated numbers — they are the numbers written in the squares of the stripe. These numbers are integer and do not exceed 10000 in absolute value.

Output the amount of ways to cut the stripe into two non-empty pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece. Don't forget that it's allowed to cut the stripe along the squares' borders only.

Input

The first input line contains integer n (1 ≤ n ≤ 105) — amount of squares in the stripe. The second line contains n space-separated numbers — they are the numbers written in the squares of the stripe. These numbers are integer and do not exceed 10000 in absolute value.

Output

Output the amount of ways to cut the stripe into two non-empty pieces so that the sum of numbers from one piece is equal to the sum of numbers from the other piece. Don't forget that it's allowed to cut the stripe along the squares' borders only.

Samples

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