Problem C
Hokie Parade

Image by Gary Cope.

At Virginia Tech’s annual homecoming parade, a line of Hokies is marching down Main Street. Each Hokie has a “spirit score” represented by an integer (which can be positive, zero, or negative).

The parade organizers want to create a spectacular formation by splitting the line into two consecutive non-empty groups where the total spirit score of each group is equal.

Your task is to determine the number of ways the line can be split between two Hokies so that the sum of the spirit scores in the first group is equal to the sum in the second group.

Input

The first line contains an integer $N$ ($2 \le N \le 5 \cdot 10^5$), which is how many Hokies are in the line. The next line contains $N$ integers $s_i$ ($-10^9 \le s_i \le 10^9$), which represent the spirit score for each hokie.

Output

Output a single integer that represents the number of ways the line can be split into two consecutive non-empty groups with the sums of their spirit scores equal to each other.

Explanation

For Sample Input $1$, the parade can be split in three ways. In between position $3$ and $4$, $6$ and $7$, and $7$ and $8$.

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

3

3
1 1 1

0