Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Non-zero Segments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKolya 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

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

Examples

Input

4 1 -5 3 2

Output

1

Input

5 4 -2 3 -9 2

Output

0

Input

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

Output

6

Input

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

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2021 08:52:51 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|