#include <bits/stdc++.h>
const long long int MOD = 1e9 + 7;
const long long int inf = 1e18 + 5;
using namespace std;
long long int bs(long long int arr[], long long int l, long long int r,
                 long long int x) {
  long long int mid = 0;
  if (r >= l) {
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return bs(arr, l, mid - 1, x);
    return bs(arr, mid + 1, r, x);
  }
  return -1;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
const int max1 = 500001;
pair<int, int> st[4 * max1];
int arr[max1], arr1[max1];
void buildtree(int si, int ss, int se) {
  if (ss == se) {
    st[si].first = arr1[ss];
    st[si].second = arr1[ss];
    return;
  }
  int mid = ss + (se - ss) / 2;
  buildtree(2 * si, ss, mid);
  buildtree(2 * si + 1, mid + 1, se);
  if (arr1[mid] > arr1[mid + 1])
    st[si].first = st[2 * si].first + st[2 * si + 1].first;
  else
    st[si].second = st[2 * si].second + st[2 * si + 1].second;
}
int query(int si, int ss, int se, int qs, int qe) {
  if (qs > se || qe < ss) return inf;
  if (ss >= qs && se <= qe) return st[si].first;
  int mid = ss + (se - ss) / 2;
  int l = query(2 * si, ss, mid, qs, qe);
  int r = query(2 * si + 1, mid + 1, se, qs, qe);
  return min(l, r);
}
int geteven(int si, int ss, int se, int qs, int qe) {
  if (ss > qe || se < qs) return 0;
  if (ss >= qs && se <= qe) return st[si].second;
  int mid = ss + (se - ss) / 2;
  int l = geteven(2 * si, ss, mid, qs, qe);
  int r = geteven(2 * si + 1, mid + 1, se, qs, qe);
  return l + r;
}
int getodd(int si, int ss, int se, int qs, int qe) {
  if (qs > se || qe < ss) return 0;
  if (ss >= qs && se <= qe) return st[si].first;
  int mid = ss + (se - ss) / 2;
  int l = getodd(2 * si, ss, mid, qs, qe);
  int r = getodd(2 * si + 1, mid + 1, se, qs, qe);
  return l + r;
}
void update(int si, int ss, int se, int qi, int newval) {
  if (ss == se) {
    if (arr[ss] % 2 == 1)
      st[si] = {0, 1};
    else
      st[si] = {1, 0};
    arr[ss] = newval;
    return;
  }
  int mid = ss + (se - ss) / 2;
  if (qi <= mid)
    update(2 * si, ss, mid, qi, newval);
  else
    update(2 * si + 1, mid + 1, se, qi, newval);
  st[si].first = st[2 * si].first + st[2 * si + 1].first;
  st[si].second = st[2 * si].second + st[2 * si + 1].second;
}
long long int bin_exp(long long int x, long long int n) {
  long long int res = 1;
  while (n) {
    if (n & 1) res = (res * x) % MOD;
    n /= 2;
    x = (x * x) % MOD;
  }
  return res;
}
long long int fermi(long long int a, long long int b) {
  return (a % MOD * (bin_exp(b, MOD - 2) % MOD)) % MOD;
}
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  long long int k = min(r, n - r);
  for (long long int i = 0; i < k; i++) {
    ans = (ans % MOD * (n - i) % MOD) % MOD;
    ans = fermi(ans, i + 1);
  }
  return ans % MOD;
}
bool isPrime(long long int n) {
  long long int flag = 1;
  for (long long int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      flag = 0;
      break;
    }
  }
  if (n <= 1)
    flag = 0;
  else if (n == 2)
    flag = 1;
  if (flag == 1)
    return true;
  else
    return false;
}
void solve() {
  long long int n, x, sum = 0, ans = 0;
  cin >> n;
  map<long long int, bool> mp;
  for (long long int i = 0; i < n; i++) {
    cin >> x;
    sum += x;
    if (!sum || mp[sum]) {
      ans++;
      sum = x;
      mp.clear();
      mp[sum] = 1;
    }
    mp[sum] = 1;
  }
  cout << ans << "\n";
}
int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  ;
  long long int t = 1;
  while (t--) solve();
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Kolya got an integer array a_1, a_2, ..., 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 ≤ n ≤ 200 000) — the number of elements in Kolya's array.

The second line of the input contains n integers a_1, a_2, ..., a_n (-10^{9} ≤ a_i ≤ 10^{9}, a_i ≠ 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.

### Response

```cpp
#include <bits/stdc++.h>
const long long int MOD = 1e9 + 7;
const long long int inf = 1e18 + 5;
using namespace std;
long long int bs(long long int arr[], long long int l, long long int r,
                 long long int x) {
  long long int mid = 0;
  if (r >= l) {
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return bs(arr, l, mid - 1, x);
    return bs(arr, mid + 1, r, x);
  }
  return -1;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
const int max1 = 500001;
pair<int, int> st[4 * max1];
int arr[max1], arr1[max1];
void buildtree(int si, int ss, int se) {
  if (ss == se) {
    st[si].first = arr1[ss];
    st[si].second = arr1[ss];
    return;
  }
  int mid = ss + (se - ss) / 2;
  buildtree(2 * si, ss, mid);
  buildtree(2 * si + 1, mid + 1, se);
  if (arr1[mid] > arr1[mid + 1])
    st[si].first = st[2 * si].first + st[2 * si + 1].first;
  else
    st[si].second = st[2 * si].second + st[2 * si + 1].second;
}
int query(int si, int ss, int se, int qs, int qe) {
  if (qs > se || qe < ss) return inf;
  if (ss >= qs && se <= qe) return st[si].first;
  int mid = ss + (se - ss) / 2;
  int l = query(2 * si, ss, mid, qs, qe);
  int r = query(2 * si + 1, mid + 1, se, qs, qe);
  return min(l, r);
}
int geteven(int si, int ss, int se, int qs, int qe) {
  if (ss > qe || se < qs) return 0;
  if (ss >= qs && se <= qe) return st[si].second;
  int mid = ss + (se - ss) / 2;
  int l = geteven(2 * si, ss, mid, qs, qe);
  int r = geteven(2 * si + 1, mid + 1, se, qs, qe);
  return l + r;
}
int getodd(int si, int ss, int se, int qs, int qe) {
  if (qs > se || qe < ss) return 0;
  if (ss >= qs && se <= qe) return st[si].first;
  int mid = ss + (se - ss) / 2;
  int l = getodd(2 * si, ss, mid, qs, qe);
  int r = getodd(2 * si + 1, mid + 1, se, qs, qe);
  return l + r;
}
void update(int si, int ss, int se, int qi, int newval) {
  if (ss == se) {
    if (arr[ss] % 2 == 1)
      st[si] = {0, 1};
    else
      st[si] = {1, 0};
    arr[ss] = newval;
    return;
  }
  int mid = ss + (se - ss) / 2;
  if (qi <= mid)
    update(2 * si, ss, mid, qi, newval);
  else
    update(2 * si + 1, mid + 1, se, qi, newval);
  st[si].first = st[2 * si].first + st[2 * si + 1].first;
  st[si].second = st[2 * si].second + st[2 * si + 1].second;
}
long long int bin_exp(long long int x, long long int n) {
  long long int res = 1;
  while (n) {
    if (n & 1) res = (res * x) % MOD;
    n /= 2;
    x = (x * x) % MOD;
  }
  return res;
}
long long int fermi(long long int a, long long int b) {
  return (a % MOD * (bin_exp(b, MOD - 2) % MOD)) % MOD;
}
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  long long int k = min(r, n - r);
  for (long long int i = 0; i < k; i++) {
    ans = (ans % MOD * (n - i) % MOD) % MOD;
    ans = fermi(ans, i + 1);
  }
  return ans % MOD;
}
bool isPrime(long long int n) {
  long long int flag = 1;
  for (long long int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      flag = 0;
      break;
    }
  }
  if (n <= 1)
    flag = 0;
  else if (n == 2)
    flag = 1;
  if (flag == 1)
    return true;
  else
    return false;
}
void solve() {
  long long int n, x, sum = 0, ans = 0;
  cin >> n;
  map<long long int, bool> mp;
  for (long long int i = 0; i < n; i++) {
    cin >> x;
    sum += x;
    if (!sum || mp[sum]) {
      ans++;
      sum = x;
      mp.clear();
      mp[sum] = 1;
    }
    mp[sum] = 1;
  }
  cout << ans << "\n";
}
int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  ;
  long long int t = 1;
  while (t--) solve();
  return 0;
}

```