你现在拥有n个数字，你可以删掉其中一个数字剩下的数按照原顺序排列，那么奇数位的数的和与偶数位的数的和是否相等，去掉的数可以是任意一个，问有多少种情况能使之相等。

Input

1 <= n <= 2e5 ai <= 1e4

Output

输出有多少种情况能使之相等

Samples

7
5 5 4 5 5 5 6

2

8
4 8 8 7 8 4 4 5

2

9
2 3 4 2 2 3 2 2 4

3

Note

第一个样例可以删去[1,2].

第二个样例可以删去[2, 3].

第三个样例可以删去[4, 5, 9].