#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template <typename T>
bool chmax(T &x, const T &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
void in() {}
template <typename Head, typename... Tail>
void in(Head &&head, Tail &&...tail) {
  cin >> head;
  in(forward<Tail>(tail)...);
}
void out() { cout << '\n'; }
template <typename Head, typename... Tail>
void out(Head &&head, Tail &&...tail) {
  cout << head << ' ';
  out(forward<Tail>(tail)...);
}
void outn() {}
template <typename Head, typename... Tail>
void outn(Head &&head, Tail &&...tail) {
  cout << head << '\n';
  outn(forward<Tail>(tail)...);
}
template <typename T, typename U>
void in(pair<T, U> &p) {
  cin >> p.first >> p.second;
}
template <typename T, typename U>
void out(pair<T, U> p) {
  cout << p.first << ' ' << p.second << '\n';
}
using vi = vector<int>;
using vll = vector<ll>;
template <typename T>
void vin(vector<T> &a) {
  for (int i = 0; i < (int)a.size(); i++) cin >> a[i];
}
template <typename T>
void vout(const vector<T> &a) {
  for (auto &e : a) cout << e << ' ';
  cout << '\n';
}
template <typename T>
void voutn(const vector<T> &a) {
  for (auto &e : a) cout << e << '\n';
}
template <typename T>
void unique(vector<T> &a) {
  sort(a.begin(), a.end()), a.erase(unique(a.begin(), a.end()), a.end());
}
vector<int> iota(int n) {
  vector<int> ret(n);
  iota(ret.begin(), ret.end(), 0);
  return ret;
}
template <typename T>
vector<int> iota(const vector<T> &a, bool greater = false) {
  vector<int> ret = iota((int)a.size());
  sort(ret.begin(), ret.end(),
       [&](int i, int j) { return (a[i] < a[j]) ^ greater; });
  return ret;
}
struct io_setup {
  io_setup() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);
  }
} io_setup;
const int MOD = 1000000007;
template <typename Monoid>
struct Segment_Tree {
  using F = function<Monoid(Monoid, Monoid)>;
  int n;
  vector<Monoid> seg;
  const F f;
  const Monoid e1;
  Segment_Tree(const vector<Monoid> &v, const F &f, const Monoid &e1)
      : f(f), e1(e1) {
    int m = (int)v.size();
    n = 1;
    while (n < m) n <<= 1;
    seg.assign(2 * n, e1);
    copy(v.begin(), v.end(), seg.begin() + n);
    for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
  }
  void change(int i, const Monoid &x) {
    seg[i += n] = x;
    while (i >>= 1) {
      seg[i] = f(seg[2 * i], seg[2 * i + 1]);
    }
  }
  Monoid query(int l, int r) const {
    Monoid ret = e1;
    l += n, r += n;
    while (l < r) {
      if (l & 1) ret = f(ret, seg[l++]);
      if (r & 1) ret = f(ret, seg[--r]);
      l >>= 1, r >>= 1;
    }
    return ret;
  }
  Monoid operator[](int i) const { return seg[n + i]; }
  template <typename C>
  int find_subtree(int i, const C &check, const Monoid &x, Monoid &M,
                   bool type) const {
    while (i < n) {
      Monoid nxt = type ? f(seg[2 * i + type], M) : f(M, seg[2 * i + type]);
      if (check(nxt, x))
        i = 2 * i + type;
      else
        M = nxt, i = 2 * i + (type ^ 1);
    }
    return i - n;
  }
  template <typename C>
  int find_first(int l, const C &check, const Monoid &x) const {
    Monoid L = e1;
    int a = l + n, b = n + n;
    while (a < b) {
      if (a & 1) {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt, x)) return find_subtree(a, check, x, L, false);
        L = nxt, a++;
      }
      a >>= 1, b >>= 1;
    }
    return n;
  }
  template <typename C>
  int find_last(int r, const C &check, const Monoid &x) const {
    Monoid R = e1;
    int a = n, b = r + n;
    while (a < b) {
      if (b & 1 || a == 1) {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt, x)) return find_subtree(b, check, x, R, true);
        R = nxt;
      }
      a >>= 1, b >>= 1;
    }
    return -1;
  }
};
int main() {
  int N;
  in(N);
  vector<ll> a(N);
  vin(a);
  auto f = [](ll x, ll y) { return max(x, y); };
  auto c = [](ll x, ll y) { return x >= y; };
  vll s(N + 1, 0);
  for (int i = 0; i < N; i++) s[i + 1] = s[i] + a[i];
  vll v(N);
  for (int i = 0; i < N; i++) v[i] = a[i] - s[i];
  Segment_Tree<ll> seg(v, f, -INF);
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    int ptr = lower_bound(s.begin(), s.end(), a[i] + s[i + 1]) - begin(s);
    if (ptr == N + 1) continue;
    ptr--;
    if (ptr < i + 2) ptr = i + 2;
    while (ptr < N) {
      if ((a[i] ^ a[ptr]) == s[ptr] - s[i + 1]) ans++;
      ptr = seg.find_first(ptr + 1, c, -a[i] - s[i + 1]);
    }
  }
  out(ans);
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Yurii is sure he can do everything. Can he solve this task, though?

He has an array a consisting of n positive integers. Let's call a subarray a[l...r] good if the following conditions are simultaneously satisfied: 

  * l+1 ≤ r-1, i. e. the subarray has length at least 3; 
  * (a_l ⊕ a_r) = (a_{l+1}+a_{l+2}+…+a_{r-2}+a_{r-1}), where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 



In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements. 

Yurii wants to calculate the total number of good subarrays. What is it equal to?

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

Input

The first line contains a single integer n (3 ≤ n ≤ 2⋅ 10^5) — the length of a. 

The second line contains n integers a_1,a_2,…,a_n (1 ≤ a_i < 2^{30}) — elements of a. 

Output

Output a single integer — the number of good subarrays. 

Examples

Input


8
3 1 2 3 1 2 3 15


Output


6

Input


10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854


Output


2

Note

There are 6 good subarrays in the example: 

  * [3,1,2] (twice) because (3 ⊕ 2) = 1; 
  * [1,2,3] (twice) because (1 ⊕ 3) = 2; 
  * [2,3,1] because (2 ⊕ 1) = 3; 
  * [3,1,2,3,1,2,3,15] because (3 ⊕ 15) = (1+2+3+1+2+3). 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template <typename T>
bool chmax(T &x, const T &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
void in() {}
template <typename Head, typename... Tail>
void in(Head &&head, Tail &&...tail) {
  cin >> head;
  in(forward<Tail>(tail)...);
}
void out() { cout << '\n'; }
template <typename Head, typename... Tail>
void out(Head &&head, Tail &&...tail) {
  cout << head << ' ';
  out(forward<Tail>(tail)...);
}
void outn() {}
template <typename Head, typename... Tail>
void outn(Head &&head, Tail &&...tail) {
  cout << head << '\n';
  outn(forward<Tail>(tail)...);
}
template <typename T, typename U>
void in(pair<T, U> &p) {
  cin >> p.first >> p.second;
}
template <typename T, typename U>
void out(pair<T, U> p) {
  cout << p.first << ' ' << p.second << '\n';
}
using vi = vector<int>;
using vll = vector<ll>;
template <typename T>
void vin(vector<T> &a) {
  for (int i = 0; i < (int)a.size(); i++) cin >> a[i];
}
template <typename T>
void vout(const vector<T> &a) {
  for (auto &e : a) cout << e << ' ';
  cout << '\n';
}
template <typename T>
void voutn(const vector<T> &a) {
  for (auto &e : a) cout << e << '\n';
}
template <typename T>
void unique(vector<T> &a) {
  sort(a.begin(), a.end()), a.erase(unique(a.begin(), a.end()), a.end());
}
vector<int> iota(int n) {
  vector<int> ret(n);
  iota(ret.begin(), ret.end(), 0);
  return ret;
}
template <typename T>
vector<int> iota(const vector<T> &a, bool greater = false) {
  vector<int> ret = iota((int)a.size());
  sort(ret.begin(), ret.end(),
       [&](int i, int j) { return (a[i] < a[j]) ^ greater; });
  return ret;
}
struct io_setup {
  io_setup() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);
  }
} io_setup;
const int MOD = 1000000007;
template <typename Monoid>
struct Segment_Tree {
  using F = function<Monoid(Monoid, Monoid)>;
  int n;
  vector<Monoid> seg;
  const F f;
  const Monoid e1;
  Segment_Tree(const vector<Monoid> &v, const F &f, const Monoid &e1)
      : f(f), e1(e1) {
    int m = (int)v.size();
    n = 1;
    while (n < m) n <<= 1;
    seg.assign(2 * n, e1);
    copy(v.begin(), v.end(), seg.begin() + n);
    for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
  }
  void change(int i, const Monoid &x) {
    seg[i += n] = x;
    while (i >>= 1) {
      seg[i] = f(seg[2 * i], seg[2 * i + 1]);
    }
  }
  Monoid query(int l, int r) const {
    Monoid ret = e1;
    l += n, r += n;
    while (l < r) {
      if (l & 1) ret = f(ret, seg[l++]);
      if (r & 1) ret = f(ret, seg[--r]);
      l >>= 1, r >>= 1;
    }
    return ret;
  }
  Monoid operator[](int i) const { return seg[n + i]; }
  template <typename C>
  int find_subtree(int i, const C &check, const Monoid &x, Monoid &M,
                   bool type) const {
    while (i < n) {
      Monoid nxt = type ? f(seg[2 * i + type], M) : f(M, seg[2 * i + type]);
      if (check(nxt, x))
        i = 2 * i + type;
      else
        M = nxt, i = 2 * i + (type ^ 1);
    }
    return i - n;
  }
  template <typename C>
  int find_first(int l, const C &check, const Monoid &x) const {
    Monoid L = e1;
    int a = l + n, b = n + n;
    while (a < b) {
      if (a & 1) {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt, x)) return find_subtree(a, check, x, L, false);
        L = nxt, a++;
      }
      a >>= 1, b >>= 1;
    }
    return n;
  }
  template <typename C>
  int find_last(int r, const C &check, const Monoid &x) const {
    Monoid R = e1;
    int a = n, b = r + n;
    while (a < b) {
      if (b & 1 || a == 1) {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt, x)) return find_subtree(b, check, x, R, true);
        R = nxt;
      }
      a >>= 1, b >>= 1;
    }
    return -1;
  }
};
int main() {
  int N;
  in(N);
  vector<ll> a(N);
  vin(a);
  auto f = [](ll x, ll y) { return max(x, y); };
  auto c = [](ll x, ll y) { return x >= y; };
  vll s(N + 1, 0);
  for (int i = 0; i < N; i++) s[i + 1] = s[i] + a[i];
  vll v(N);
  for (int i = 0; i < N; i++) v[i] = a[i] - s[i];
  Segment_Tree<ll> seg(v, f, -INF);
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    int ptr = lower_bound(s.begin(), s.end(), a[i] + s[i + 1]) - begin(s);
    if (ptr == N + 1) continue;
    ptr--;
    if (ptr < i + 2) ptr = i + 2;
    while (ptr < N) {
      if ((a[i] ^ a[ptr]) == s[ptr] - s[i + 1]) ans++;
      ptr = seg.find_first(ptr + 1, c, -a[i] - s[i + 1]);
    }
  }
  out(ans);
}

```