C. Eugene and an array

Eugene likes working with arrays. And today he needs your help in solving one challenging task.

An array c is a subarray of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Let’s call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array [−1,2,−3] is good, as all arrays [−1], [−1,2], [−1,2,−3], [2], [2,−3], [−3] have nonzero sums of elements. However, array [−1,2,−1,−3] isn’t good, as his subarray [−1,2,−1] has sum of elements equal to 0.

Help Eugene to calculate the number of nonempty good subarrays of a given array a.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 2×105) — the length of array a.

The second line of the input contains n integers a1,a2,…,an (−109 ≤ ai ≤ 109 ) — the elements of aa.

Output

Output a single integer — the number of good subarrays of a.

Examples

input

3
1 2 -3

output

5

input

3
41 -41 41

output

3

Note

In the first sample, the following subarrays are good: [1], [1,2], [2], [2,−3], [−3]. However, the subarray [1,2,−3] isn’t good, as its subarray [1,2,−3] has sum of elements equal to 0.

In the second sample, three subarrays of size 1 are the only good subarrays. At the same time, the subarray [41,−41,41] isn’t good, as its subarray [41,−41] has sum of elements equal to 0.

Problem solving

题意定义一个数组如果没有区间和等于0的的段是 good。然后给你一个数组,统计出这个数组有多少个非空子数组是 good

比如[2,-2,3],区间[1,2]的和为0,所以子段[1,2]与[1,3]都是isn’t good

#include<bits/stdc++.h>
#define fi        first
#define se        second
#define pb        push_back
#define PI        acos(-1)
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<ll,ll>   PLL;
typedef pair<ll,int>  PLI;
const int INF = 0X3F3F3F3F;
const int MIN = -(1<<30);
const ll N = 2e5+7;
int a[N];
inline void solve()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    map<ll,ll> mp;
    ll sum=0,k=-1;
    mp[0]=0;
    ll ans = 0;
    for(int i=1; i<=n; i++)
    {
        sum+=a[i];
        if(mp.count(sum)) k=max(k,mp[sum]);
        ans+=i-k-1;
        mp[sum]=i;
    }
    cout<<ans<<endl;
}
int main()
{
    IOS();
    solve();
    return 0;
}

一个好奇的人