Non-zero Segments

Description:

Input:

The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of elements in Kolya's array.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}, a_i \neq 0$$$) — the description of Kolya's array.

Output:

Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $$$0$$$.

Sample Input:

4
1 -5 3 2

Sample Output:

1

Sample Input:

5
4 -2 3 -9 2

Sample Output:

0

Sample Input:

9
-1 1 -1 1 -1 1 1 -1 -1

Sample Output:

6

Sample Input:

8
16 -5 -11 -15 10 5 4 -4

Sample Output:

3

Note:

Consider the first example. There is only one subsegment with the sum $$$0$$$. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer $$$1$$$ between second and third elements of the array.

There are no subsegments having sum $$$0$$$ in the second example so you don't need to do anything.