#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define gcd __gcd
#define lcm(a, b) (a*b)/gcd(a, b)
#define pcount __builtin_popcount
#define pcountll __builtin_popcountll
#define nxtperm next_permutation
//primitive roots: 998244353 - 3; 7340033 - 5
//#pragma 03
//#pragma GCC target ("sse4.2")
const ll mod = 1000000007;
const double PI = acos(-1.);
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef complex<double> cd;
ll n;
int lookup[20000050];
// We have N <= 200000
// Case 1: 1 <= N <= 2000: brute force o(n^2 log n).
// Case 2: 2000 < N <= 20000: lookup table
// Case 3: FFT.
void solvebrS()
{
int pre[20050], tmp, cnt = 0; pre[0] = 0;
for(int i=1;i<=n;i++) cin >> tmp, pre[i] = pre[i-1] + tmp;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
lookup[pre[i] - pre[j]] = 1;
for(int i=1;i<=200000;i++) cnt += lookup[i];
cout << cnt - 1;
}
void solvebrN()
{
int pre[2005], tmp; pre[0] = 0;
vector<ll> a;
for(int i=1;i<=n;i++) cin >> tmp, pre[i] = pre[i-1] + tmp;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
a.pb(pre[i] - pre[j]);
sort(a.begin(), a.end());
int r = 0;
for(int i=1;i<a.size();i++) if(a[i] != a[i-1]) r++;
cout << r;
}
int rev[5000000];
void fft(vector<cd> &a, int n, bool inv)
{
int lg = log2(n);
for(int i=0;i<n;++i)
{
rev[i] = (rev[i>>1] | ((i & 1) << lg)) >> 1;
swap(a[i], (i<rev[i]?a[rev[i]]:a[i]));
}
for(int l=2;l<=n;l<<=1)
{
double angle = 2 * PI / l * (inv ? -1 : 1);
cd wn(cos(angle), sin(angle));
for(int i=0;i<n;i+=l)
{
cd w(1);
for(int j=0;2*j<l;j++)
{
cd u = a[i+j], v = w * a[i+j+l/2];
a[i+j] = u + v;
a[i+j+l/2] = u - v;
w *= wn;
}
}
}
if(inv) for(auto &x:a) x /= n;
}
vector<int> mul(vector<cd> a, vector<cd> b)
{
vector<cd> a_ = a, b_ = b;
int n = 1, s = a.size() + b.size();
while(n < s) n <<= 1;
a_.resize(n);
b_.resize(n);
fft(a_, n, 0);
fft(b_, n, 0);
for(int i=0;i<n;i++) a_[i] *= b_[i];
fft(a_, n, 1);
vi ans(n);
for(int i=0;i<n;i++) ans[i] = round(a_[i].real());
return ans;
}
void solve()
{
vector<cd> a, b;
vector<int> pre;
a.assign(2000000, 0);
b.assign(2000000, 0);
pre.assign(200500, 0);
int tmp;
for(int i=1;i<=n;i++) cin >> tmp, pre[i] = pre[i-1] + tmp;
b[pre[n]] = 1;
for(int i=1;i<=n;i++)
{
a[pre[i]] = 1;
b[pre[n] - pre[i]] = 1;
}
vi C = mul(a, b);
int ans = 0;
for(int i=pre[n]+1;i<C.size();i++) ans += (C[i]>0);
cout << ans-1;
}
signed main()
{
// freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
fast_cin();
cin >> n;
if(n <= 2000) solvebrN();
else if(n <= 20000) solvebrS();
else solve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBmYXN0X2NpbigpIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKE5VTEwpCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBnY2QgX19nY2QKI2RlZmluZSBsY20oYSwgYikgKGEqYikvZ2NkKGEsIGIpIAojZGVmaW5lIHBjb3VudCBfX2J1aWx0aW5fcG9wY291bnQgCiNkZWZpbmUgcGNvdW50bGwgX19idWlsdGluX3BvcGNvdW50bGwKI2RlZmluZSBueHRwZXJtIG5leHRfcGVybXV0YXRpb24KLy9wcmltaXRpdmUgcm9vdHM6IDk5ODI0NDM1MyAtIDM7IDczNDAwMzMgLSA1Ci8vI3ByYWdtYSAwMwovLyNwcmFnbWEgR0NDIHRhcmdldCAoInNzZTQuMiIpCmNvbnN0IGxsIG1vZCA9IDEwMDAwMDAwMDc7CmNvbnN0IGRvdWJsZSBQSSA9IGFjb3MoLTEuKTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CnR5cGVkZWYgdHJlZTxpbnQsIG51bGxfdHlwZSwgbGVzczxpbnQ+LHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+IG9yZGVyZWRfc2V0Owp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IGlpOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3RvcjxpaT4gdmlpOwp0eXBlZGVmIGNvbXBsZXg8ZG91YmxlPiBjZDsKCmxsIG47ICAKaW50IGxvb2t1cFsyMDAwMDA1MF07IAovLyBXZSBoYXZlIE4gPD0gMjAwMDAwCi8vIENhc2UgMTogMSA8PSBOIDw9IDIwMDA6IGJydXRlIGZvcmNlIG8obl4yIGxvZyBuKS4gCi8vIENhc2UgMjogMjAwMCA8IE4gPD0gMjAwMDA6IGxvb2t1cCB0YWJsZQovLyBDYXNlIDM6IEZGVC4gIAoKdm9pZCBzb2x2ZWJyUygpCnsKCWludCBwcmVbMjAwNTBdLCB0bXAsIGNudCA9IDA7IHByZVswXSA9IDA7IAoJZm9yKGludCBpPTE7aTw9bjtpKyspIGNpbiA+PiB0bXAsIHByZVtpXSA9IHByZVtpLTFdICsgdG1wOyAKCWZvcihpbnQgaT0xO2k8PW47aSsrKSAKCQlmb3IoaW50IGo9MDtqPGk7aisrKSAKCQkJbG9va3VwW3ByZVtpXSAtIHByZVtqXV0gPSAxOyAKCWZvcihpbnQgaT0xO2k8PTIwMDAwMDtpKyspIGNudCArPSBsb29rdXBbaV07ICAKCWNvdXQgPDwgY250IC0gMTsKfQoKdm9pZCBzb2x2ZWJyTigpCnsKCWludCBwcmVbMjAwNV0sIHRtcDsgcHJlWzBdID0gMDsgCgl2ZWN0b3I8bGw+IGE7Cglmb3IoaW50IGk9MTtpPD1uO2krKykgY2luID4+IHRtcCwgcHJlW2ldID0gcHJlW2ktMV0gKyB0bXA7IAoJZm9yKGludCBpPTE7aTw9bjtpKyspIAoJCWZvcihpbnQgaj0wO2o8aTtqKyspIAoJCQlhLnBiKHByZVtpXSAtIHByZVtqXSk7IAoJc29ydChhLmJlZ2luKCksIGEuZW5kKCkpOyAKCWludCByID0gMDsgCglmb3IoaW50IGk9MTtpPGEuc2l6ZSgpO2krKykgaWYoYVtpXSAhPSBhW2ktMV0pIHIrKzsgCgljb3V0IDw8IHI7IAp9CgppbnQgcmV2WzUwMDAwMDBdOwp2b2lkIGZmdCh2ZWN0b3I8Y2Q+ICZhLCBpbnQgbiwgYm9vbCBpbnYpCnsKCWludCBsZyA9IGxvZzIobik7Cglmb3IoaW50IGk9MDtpPG47KytpKSAKCXsKCQlyZXZbaV0gPSAocmV2W2k+PjFdIHwgKChpICYgMSkgPDwgbGcpKSA+PiAxOwoJCXN3YXAoYVtpXSwgKGk8cmV2W2ldP2FbcmV2W2ldXTphW2ldKSk7ICAKCX0KCWZvcihpbnQgbD0yO2w8PW47bDw8PTEpCgl7CgkJZG91YmxlIGFuZ2xlID0gMiAqIFBJIC8gbCAqIChpbnYgPyAtMSA6IDEpOyAKCQljZCB3bihjb3MoYW5nbGUpLCBzaW4oYW5nbGUpKTsgCgkJZm9yKGludCBpPTA7aTxuO2krPWwpCgkJewoJCQljZCB3KDEpOyAKCQkJZm9yKGludCBqPTA7MipqPGw7aisrKSAKCQkJewoJCQkJY2QgdSA9IGFbaStqXSwgdiA9IHcgKiBhW2kraitsLzJdOyAKCQkJCWFbaStqXSA9IHUgKyB2OyAKCQkJCWFbaStqK2wvMl0gPSB1IC0gdjsgCgkJCQl3ICo9IHduOyAKCQkJfQoJCX0KCX0KCWlmKGludikgZm9yKGF1dG8gJng6YSkgeCAvPSBuOyAKfQoKdmVjdG9yPGludD4gbXVsKHZlY3RvcjxjZD4gYSwgdmVjdG9yPGNkPiBiKQp7Cgl2ZWN0b3I8Y2Q+IGFfID0gYSwgYl8gPSBiOyAKCWludCBuID0gMSwgcyA9IGEuc2l6ZSgpICsgYi5zaXplKCk7Cgl3aGlsZShuIDwgcykgbiA8PD0gMTsgCglhXy5yZXNpemUobik7IAoJYl8ucmVzaXplKG4pOwoJZmZ0KGFfLCBuLCAwKTsKCWZmdChiXywgbiwgMCk7Cglmb3IoaW50IGk9MDtpPG47aSsrKSBhX1tpXSAqPSBiX1tpXTsgCglmZnQoYV8sIG4sIDEpOwoJdmkgYW5zKG4pOyAKCWZvcihpbnQgaT0wO2k8bjtpKyspIGFuc1tpXSA9IHJvdW5kKGFfW2ldLnJlYWwoKSk7IAoJcmV0dXJuIGFuczsgIAp9Cgp2b2lkIHNvbHZlKCkKewoJdmVjdG9yPGNkPiBhLCBiOwoJdmVjdG9yPGludD4gcHJlOyAKCWEuYXNzaWduKDIwMDAwMDAsIDApOyAKCWIuYXNzaWduKDIwMDAwMDAsIDApOyAKCXByZS5hc3NpZ24oMjAwNTAwLCAwKTsKCWludCB0bXA7IAoJZm9yKGludCBpPTE7aTw9bjtpKyspIGNpbiA+PiB0bXAsIHByZVtpXSA9IHByZVtpLTFdICsgdG1wOyAKCWJbcHJlW25dXSA9IDE7Cglmb3IoaW50IGk9MTtpPD1uO2krKykgCgl7CgkJYVtwcmVbaV1dID0gMTsgCgkJYltwcmVbbl0gLSBwcmVbaV1dID0gMTsgCgl9Cgl2aSBDID0gbXVsKGEsIGIpOwoJaW50IGFucyA9IDA7ICAKCWZvcihpbnQgaT1wcmVbbl0rMTtpPEMuc2l6ZSgpO2krKykgYW5zICs9IChDW2ldPjApOyAKCWNvdXQgPDwgYW5zLTE7IAp9CgpzaWduZWQgbWFpbigpCnsKLy8JZnJlb3BlbigiaW4udHh0IiwgInIiLCBzdGRpbik7IGZyZW9wZW4oIm91dC50eHQiLCAidyIsIHN0ZG91dCk7CglmYXN0X2NpbigpOwoJY2luID4+IG47IAoJaWYobiA8PSAyMDAwKSBzb2x2ZWJyTigpOyAKCWVsc2UgaWYobiA8PSAyMDAwMCkgc29sdmViclMoKTsgCgllbHNlIHNvbHZlKCk7IAp9Cg==