Jerry Yang is going to visit Berkeley for the launch of his new book and naturally there’s a lot of excitement amongst students in the campus. He wants to make the launch interesting by playing a game. The following are the rules of the game -
All students stand in a single line.
Every student gets a card which contains a random number between -10 and 10 (both inclusive)
Every group that has the sum of values in their card as +1 or -1 gets a signed copy of the book. A group is defined to be a continuous set of students >=1 (a single student is considered a group of size 1)
A student can be a part of multiple groups.
Since you are in-charge of distributing the books, given the card values of students, can you figure out how many groups will get signed copies of the book?
For some testcases, output will only fit in 64 bit integers
Input Format
The first line contains the number N, N lines follow each line containing 1 integer.
Output Format
Write the total number of groups as the answer.
Sample input #01:
a = [1, -1, 1, -1, 1 ]
Sample output #01:
9
Constraint:
Number of students <= 10^6
Explanation:
There are nine groups:
1
-1
1
-1
1
1 -1 1
-1 1 -1
1 -1 1
1 -1 1 -1 1