D. Non-zero Segments

D. Non-zero Segments

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kolya got an integer array a1,a2,…,ana1,a2,…,an. The array can contain both positive and negative integers, but Kolya doesn't like 00, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be 00. 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 00. 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, 00, 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 00.

Input

The first line of the input contains one integer nn (2≤n≤2000002≤n≤200000) — the number of elements in Kolya's array.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109,ai≠0−109≤ai≤109,ai≠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 00.

Examples

input

Copy

4
1 -5 3 2

output

Copy

1

input

Copy

5
4 -2 3 -9 2

output

Copy

0

input

Copy

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

output

Copy

6

input

Copy

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

output

Copy

3

Note

Consider the first example. There is only one subsegment with the sum 00. 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 11 between second and third elements of the array.

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

连续子段和为0无非两种情况，一种是1个或多个小区间不交叉，各自和为0，此时答案就是这些区间的个数。第二种就是交叉，包含的和为0的区间，此时我们可以发现，我们只需要从前往后扫，发现一个和为0的，就把答案加1，再从该位置重新计数。这样即使有包含情况存在，我们把被包含的改成巨大的数字，那么大区间也就不用修改了，即使有交叉的，我们把交叉的那部分修改成巨大数，再从新起点开始，那么这个交叉的也被瓦解了。这里体现的是一种贪心的思想，及能修改就修改，先修改一定最优。

判断区间和是0的快速方法是，哈希表存前缀，重复出现说明出现了当前第一个和是0的区间

#include<iostream>
# include<algorithm>
# include<unordered_map>

using namespace std;
typedef long long int  ll;

unordered_map<ll,bool>mp;
int main ()
{

   ll n,ans=0,x,nowsum=0;
   cin>>n;
   mp[0]=1;
   for(int i=1;i<=n;i++)
   {
       cin>>x;
       nowsum+=x;
       if(mp.find(nowsum)==mp.end())
       {
           mp[nowsum]=1;
       }
       else
       {
           ans++;
           mp.clear();
           nowsum=x;
           mp[x]=1;
           mp[0]=1;
       }

   }
   cout<<ans;
    return 0;

}