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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int INT() {
	int in; scanf("%d", &in);
	return in;
}

vector <int> pref;

int sum(int l, int r) {
	return pref[r]-(l ? pref[l-1] : 0);
}

int main() {
	int n=INT();
	vector <int> a(n);
	for(int &x : a) x=INT();
	pref.resize(n);
	pref[0]=a[0];
	for(int i=1; i<n; ++i) pref[i]=pref[i-1]+a[i];

	ll ans=0ll;
	unordered_map <int, int> p3, pi; // p3 - trzy prefiksy, pi - prefiks i przedzial
	p3[0]=1;

	int off1=0, off3=0;
	for(int x=n-1; x>=0; --x) {
		// lll
		ans+=p3[-3*a[x]-off3];
		for(int i=0; i<x; ++i) ans+=3*p3[-2*a[x]-sum(i, x)-off3]+3*p3[-a[x]-2*sum(i, x)-off3];
		for(int i=0; i<x; ++i) for(int j=i+1; j<x; ++j) ans+=6*p3[-a[x]-sum(i, x)-sum(j, x)-off3];
		//for(int i=0; i<x; ++i) for(int j=i+1; j<x; ++j) if(sum(i, x)+sum(j, x)+a[x]==0) ++ans;

		//printf("ans after lll: %lld\n", ans);

		// lrl
		for(int i=0; i<x; ++i) for(int j=i; j<x; ++j) ans+=pi[-a[x]-sum(i, j)-off1];

		//printf("ans after lrl: %lld\n", ans);

		// llr
		//ans+=pi[-2*a[x]-off1];
		for(int i=0; i<=x; ++i) for(int j=0; j<=x; ++j) ans+=pi[-sum(i, x)-sum(j, x)-off1];

		//printf("ans after llr: %lld\n", ans);

		off1+=a[x], off3+=3*a[x];

		// rrr
		++p3[3*a[x]-off3];
		for(int i=x+1; i<n; ++i) p3[2*a[x]+sum(x, i)-off3]+=3, p3[a[x]+2*sum(x, i)-off3]+=3;
		for(int i=x+1; i<n; ++i) for(int j=i+1; j<n; ++j) p3[a[x]+sum(x, i)+sum(x, j)-off3]+=6;

		// rlr
		for(int i=x+1; i<n; ++i) for(int j=i; j<n; ++j) ++pi[a[x]+sum(i, j)-off1];

		// lrr
		//++pi[2*a[x]-off1];
		for(int i=x; i<n; ++i) for(int j=x; j<n; ++j) ++pi[sum(x, i)+sum(x, j)-off1];

		/*printf("pi: ");
		for(auto &p : pi) if(p.second) printf("%d %d  ", p.first+off1, p.second);
		printf("\n");
		printf("p3: ");
		for(auto &p : p3) if(p.second) printf("%d %d  ", p.first+off3, p.second);
		printf("\n\n");*/
	}

	unordered_map <int, int> amount; // ile przedzialow o danej sumie
	for(int i=0; i<n; ++i) for(int j=i; j<n; ++j) ++amount[sum(i, j)];
	
	ll zeros=0;
	for(int i=0; i<n; ++i) for(int j=i; j<n; ++j) {
		if(sum(i, j)) ans-=amount[-2*sum(i, j)];
		else ++zeros;
	}
	if(zeros) ans-=zeros, ans-=zeros*(zeros-1ll);
	printf("%lld\n", ans);
	exit(0);
}