题目内容

在一个由 $n$ 个位置组成的圆环上，每个位置都写有一个整数。现在需要选择两个不同的位置作为分割点，将圆环分成两个连续的弧段。要求两个弧段各自包含至少一个位置，并且两个弧段上的整数之和相等。

请问一共有多少种不同的分割方案？

圆环上的位置个数 $n$ 满足 $1 \le n \le 10^5$，每个位置上的整数绝对值不超过 $10^9$。

输入描述

第一行包含一个整数 $n$，表示圆环上的位置数量。

第二行包含 $n$ 个整数，按顺时针顺序给出每个位置上的数值，相邻两个数之间用空格分隔。

输出描述

输出一个整数，表示满足条件的分割方案数。

样例1

输入

4
1 2 1 2

输出

2

说明

整个圆环的总和 $S = 6$，平分后目标值为 $\frac{S}{2} = 3$。 前缀和依次为 0, 1, 3, 4。 枚举右端点 $j$：

• $j = 2$ 时前缀和为 3，需要前缀和 0，出现次数 1，对应切口在位置 0 和 2 之间的一种方案；
• $j = 3$ 时前缀和为 4，需要前缀和 1，出现次数 1，对应切口在位置 1 和 3 之间的一种方案。 因此共有 2 种分割方案。

样例2

输入

3
1 1 1

输出

0

说明

总和 $S = 3$ 为奇数，无法分成两个和相等的整数部分，所以没有可行的分割方案，答案为 0。

样例3

输入

5
2 -1 1 2 -2

输出

2

说明

总和 $S = 2$，目标值为 $\frac{S}{2} = 1$。 前缀和依次为 0, 2, 1, 2, 4, 2。 枚举右端点 $j$：

• $j = 2$ 时前缀和为 1，需要前缀和 0，出现次数 1，找到一种方案；
• $j = 3$ 时前缀和为 2，需要前缀和 1，出现次数 1，又找到一种方案。 因此共有 2 种分割方案。

样例4

输入

1
10

输出

0

说明

圆环上只有一个位置，无法选出两个不同的位置作为分割点，因此方案数为 0。