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
#include <bits/stdc++.h>

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define vec vector
#define pb push_back
#define f first
#define s second
#define ir(a, b, x) (((a) <= (x)) && ((x) <= (b)))
#define pint pair<int, int>
#define us unsigned

using namespace std;

const int N = 500;
const int A = 21000;//3e4;
int n;
int arr[N];
ll prefixes[N+1];

const ll S = 3*N*A;

int cnt_pos[2*S+1];

int cnt_pos_plus[2*S+1];
int cnt_pos_neg[2*S+1];

int cnt_neg_plus[2*S+1];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	foru(i, n) cin >> arr[i];

	fors(i, n+1, 1) prefixes[i] = prefixes[i-1] + arr[i-1];

	//cout << "prefixes: ";
	//foru(i, n+1) cout << prefixes[i] << " ";
	//cout << "\n";

	foru(s1, n) fors(e1, n, s1) foru(es, n+1) {
		//cout << "for segment " << s1 + 1 << " - " << e1 + 1 << " and prefix " << es << " adding value ";
		//cout << prefixes[e1+1]-prefixes[s1]+prefixes[es] << " or " << prefixes[e1+1]-prefixes[s1]-prefixes[es];
		//cout << endl;
		
		cnt_pos_plus[prefixes[e1+1]-prefixes[s1]+prefixes[es] + S] ++;
		cnt_pos_neg[prefixes[e1+1]-prefixes[s1]-prefixes[es] + S] ++;

		cnt_neg_plus[-prefixes[e1+1]+prefixes[s1]+prefixes[es] + S] ++;
	}
		
	ll ans_cont = 0;
	ll diff = 0;

	foru(i, 2*S) {
		ans_cont += 1LL*cnt_pos_plus[i]*cnt_pos_neg[2*S-i]; /// 3 pos or 2 pos 1 neg
		diff += 1LL*cnt_pos_neg[i]*cnt_neg_plus[2*S-i]; /// 2 pos 1 neg or 1 pos 2 neg
	}

	//cout << "debug ans_cont " << ans_cont << endl;
	//cout << "debug diff " << diff << endl;

	foru(i, n){
		int partial_sum = 0;
		fors(j, n, i) {
			partial_sum += arr[j];
			cnt_pos[S+partial_sum] ++;
		}
	}

	foru(i, 2*S){
		ans_cont -= 1LL*(n+1)*cnt_pos[i]*cnt_pos[2*S-i]; // delete with 0 size segment
		diff -= 1LL*(n+1)*cnt_pos[i]*cnt_pos[i]; // delete with 0 size segment
	}

	//cout << "after deleting length 0\n";
	//cout << "debug ans_cont " << ans_cont << endl;
	//cout << "debug diff " << diff << endl;

	ans_cont -= diff/2;

	//cout << "after deleting reverses\n";
	//cout << "debug ans_cont " << ans_cont << endl;

	foru(i, 2*S){
		if(i == S) continue;
		
		if(ir(0, 2*S-1, 3*S-2*i)) ans_cont -= 1LL*3*cnt_pos[i]*cnt_pos[3*S-2*i]; // delete repetitions 
		//ans_cont -= 2*cnt_pos[i]*cnt_pos[S]; // delete repetitions
		//if(ir(0, 2*S-1, -S+2*i)) ans_cont -= 1*cnt_pos[i]*cnt_pos[-S+2*i]; // delete repetitions
	}

	ans_cont -= 1LL*cnt_pos[S]*(cnt_pos[S]-1)*3;
	ans_cont -= 1LL*cnt_pos[S]; /// aaa

	//cout << "after deleting repetitions\n";
	//cout << "debug ans_cont " << ans_cont << endl;
	
	ll ans = ans_cont;

	cout << ans/6 << endl;
}