beecrowd | 1900

Null Sequences

By Caio Russi, UNOESTE BR Brazil

Timelimit: 1

Chico won a list of integers on his birthday and he called his friend Mário to play with it. The play is: "Chico will choose N numbers from the list and will put them in a random sequence, and Mário will have to say if there is a Null Sequence in this new sequence at least.". Let's call Null Sequence a contiguous sequence of integers where in the sum of all elements are equals to zero.

Given the result of the first test case: (-2,-1,0,1,2).

Example Null Sequences: (-2,-1,0,1,2), (-1,0,1), (0).

Example not Null Sequences: (-1,1), (-2,0,2), (1).

Chico is furious because Mario is winning all the time, so he decided to hinder the game. Now he will not have to say wheter or not a Null Sequences, but to say how many sequences in the list are sequences Null. Now who's getting angry is Mário and you have to help him without the Chico notice.


The first line contains an integer N (1 ≤ N ≤ 105), that is the quantity of numbers chosen by Chico. In the second of the test case line contains the N integers Vi (-106Vi ≤ 106) separated by spaces representing the elements of the sequence.


For each test case print the number of sequences Null in the given sequence.

Input Sample Output Sample

-2 -1 0 1 2


1 -1 1 -1 1


1 2 3