A13806 | Non-zero Segments

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$ .

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.

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$ .