Non-zero Segments
Contest: Codeforces Round 674 (Div. 3)
Difficulty rating: 1500
Tags: constructive algorithms, data structures, greedy, sortings

Kolya got an integer array $$$a_1, a_2, \dots, a_n$$$. The array can contain both positive and negative integers, but Kolya doesn't like $$$0$$$, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be $$$0$$$. The subsegment is some consecutive segment of elements of the array.

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum $$$0$$$. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, $$$0$$$, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find 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$$$.

Input format:
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 format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
4
1 -5 3 2

Example output:
1

Example input:
5
4 -2 3 -9 2

Example output:
0

Editorial:
Firstly, let's understand that the sum of the segment $$$[l; r]$$$ is zero if $$$p_r - p_{l - 1}$$$ is zero (in other words, $$$p_{l - 1} = p_r$$$), where $$$p_i$$$ is the sum of the first $$$i$$$ elements ($$$p_0 = 0$$$).
Let's iterate over elements from left to right and add all prefix sums in the set. If we get the sum that is already in the set, we get some segment with sum $$$0$$$, and we need to fix it somehow. Let's insert some huge number before the current element in such a way that all prefix sums starting from the current element to the end will be significantly bigger than all prefix sums to the left. In words of implementation, we just get rid of all prefix sums to the left (clear the set) and continue doing the same process starting from the current element (so we just cut off the prefix of the array).
This way is optimal because we remove all segments with sum $$$0$$$ ending at the current element using only one insertion (and we need to use at least one insertion to do that).
Time complexity: $$$O(n \log{n})$$$.