1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int inf = 1e9;
const int N = 500, A = 20'000;
const int SUM_RANGE = N*A*4+3;

int cnt[SUM_RANGE];
vector<int> to_add[N+3], querys[N+3];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> a(n);
	for(int &x : a) cin >> x;

	int mx = -inf, mn = inf;
	vector<int> seg;
	for(int i = 0; i < n; ++i) {
		int sum = 0;
		for(int j = i; j < n; ++j) {
			sum += a[j];
			seg.eb(sum);
			mx = max(mx, sum);
			mn = min(mn, sum);
		}
	}
	vector<int> pref(n);
	pref[0] = a[0];
	for(int i = 1; i < n; ++i) pref[i] = pref[i-1] + a[i];

	auto get_pref = [&](int j) {
		return j >= 0 ? pref[j] : 0;
	};

	if(mx < 0 || mn > 0) {cout << 0 << '\n'; return 0;}

	int offset = max(-2*mn, -mn+mx);

	ll res = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = i; j < n; ++j) {
			for(int k = 0; k < n; ++k) {
				int s = pref[j]-get_pref(i-1)-get_pref(k-1);
				querys[k].eb(s);
			}
		}
	}

	for(int i = 0; i < n; ++i) {
		for(int j = i; j < n; ++j) {
			for(int k = 0; k < n; ++k) {
				int s = pref[j]-get_pref(i-1)+pref[k];
				to_add[k].eb(s);
			}
		}
	}

	for(int i = n-1; i >= 0; --i) {
		for(auto s : to_add[i])
			cnt[s+offset]++;

		for(auto s : querys[i])
			res += cnt[-s+offset];
	}


	ll ab = 0, bc = 0, abc = 0;
	unordered_map<int, int> cnt1, cnt2;
	for(int x : seg) {
		ab += cnt1[-x];
		bc += cnt2[-2*x];
		++cnt1[2*x];
		++cnt2[x];
		if(x == 0) ++abc;
	}

	debug(ab);
	debug(bc);
	debug(abc);
	res -= 3*(ab+bc);
	res -= abc;
	debug(res);
	res /= 6;

	cout << res << '\n';
	#ifdef LOCAL
system("grep VmPeak /proc/$PPID/status >&2");
#endif

	return 0;
}