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
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;

#include<bits/stdc++.h>
// #include<bits/extc++.h>
#include <ext/pb_ds/assoc_container.hpp>

struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;

template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

using ll = int64_t;

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;
	vector<int> psums(N+1);
	for(int i = 0; i < N; i++) psums[i+1] = psums[i] + A[i];

	int64_t ans = 0;
	int Z = 3e7 + 1;
	// i < j < k
	{
		vector<int> freq(2 * Z + 1, 0);
		for(int jl = N; jl >= 0; jl--){
			for(int il = 0; il < jl; il++){
				for(int ir = il+1; ir <= N; ir++){
					ans += freq[psums[il] - psums[ir] + psums[jl] + Z];
				}
			}
			// jr = jl
			{
				int jr = jl;
				for(int kl = jr; kl <= N; kl++){
					for(int kr = kl+1; kr <= N; kr++){
						freq[psums[kr] - psums[kl] + psums[jr] + Z]++;
					}
				}
			}
			{
				int kl = jl;
				for(int jr = jl+1; jr <= N; jr++){
					for(int kr = kl+1; kr <= N; kr++){
						freq[psums[kr] - psums[kl] + psums[jr] + Z]++;
					}
				}
			}
		}
	}
	// i = j < k
	{
		vector<int> freq(2 * Z + 1, 0);
		for(int il = N; il >= 0; il--){
			for(int ir = il+1; ir <= N; ir++){
				for(int jr = ir+1; jr <= N; jr++){
					ans += freq[psums[il] - psums[ir] + psums[il] - psums[jr] + Z];

				}
			}
			int kl = il;
			for(int kr = kl+1; kr <= N; kr++){
				freq[psums[kr] - psums[kl] + Z]++;
			}
		}
	}
	//i < j = k
	{
		vector<int> freq(2 * Z + 1, 0);
		for(int jl = N; jl >= 0; jl--){
			for(int il = 0; il < jl; il++){
				for(int ir = il+1; ir <= N; ir++){
					ans += freq[psums[il] - psums[ir] + psums[jl] + psums[jl] + Z];
				}
			}
			int jr = jl;
			for(int kr = jr+1; kr <= N; kr++){
				freq[psums[kr] + psums[jr] + Z]++;
			}
		}
	}
	// i = j = k
	{
		vector<int> freq(2 * Z + 1, 0);
		for(int ir = N; ir >= 0; ir--){
			for(int il = 0; il < ir; il++){
				ans += freq[psums[il] * 3 - psums[ir] + Z];
			}
			int jr = ir;
			for(int kr = jr+1; kr <= N; kr++){
				freq[psums[jr] + psums[kr] + Z]++;
			}
		}
	}
	cout << ans << '\n';
}