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

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define x first
#define y second
#define ir(a, x, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()

using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N;
    vec<ll> a, pref;
// #define TEST
#ifdef TEST
    N = 500;
    a.assign(N, 500);
    // rep (i, 0, N) {
    //     a[i] = i+1;
    // }
    // rep (i, N/2, N) {
    //     a[i] = i-N;
    // }
#else
    cin >> N;
    a.resize(N);
    rep (i, 0, N) cin >> a[i];
#endif
    pref.resize(N+1);
    rep (i, 1, N+1) pref[i] = pref[i-1]+a[i-1];
    const int C = int(1e8)/2;
    vec<int> ct(1e8);
    
    ll s = 0;
    rep (k, 0, N) {
        rep (i, 0, N+1) {
            rep (j, 0, i) {
                ct[pref[i]-pref[j]-pref[k] + C]++; // at k
            }
        }
        rep (i, 0, N+1) {
            rep (j, 0, i) {
                s += ct[-(pref[i]-pref[j]+pref[k+1]) + C]; // at k+1
            }
        }
    }
    
    unordered_map<ll, ll> m;
    ll zeros = 0;
    rep (i, 0, N+1) {
        rep (j, 0, i) {
            m[pref[i]-pref[j]]++;
        }
    }
    rep (i, 0, N+1) {
        rep (j, 0, i) {
            s -= 3*m[-2*(pref[i]-pref[j])];
        }
    }
    s += 2*m[0];
    // rep (i, 0, N+1) {
    //     rep (j, 0, i) { // [j, i), [k..
    //         rep (k, 0, i) {
    //             ft.add(k, pref[i]-pref[j]-pref[k]);
    //             if (k < 2 && pref[i]-pref[j]-pref[k] == -4) {
    //                 debug(j, i, k);
    //             }
    //         }
    //     }
    //     rep (j, 0, i) {
    //         rep (k, 0, i+1) { // [j, i), ...k)
    //             int _temp;
    //             s += (_temp = ft.query(k, -(pref[i]-pref[j]+pref[k])));
    //             debug(k, j, i, pref[i]-pref[j]+pref[k], _temp);
    //         }
    //     }
    // }
    
    cout << s/6 << '\n';
    
    // TODO: remove with twice the same interval
    // TODO: add with three times the same interval
    return 0;
}