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
//Jakub Nowak XIV LO Wroclaw
#include<bits/stdc++.h>
using namespace std;

#define boost ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define st first
#define nd second
const int inf = (int)(1e18)+7;

void wypisz(auto &X) {
    for(auto &x : X) cout << x << " ";
    cout << "\n";
}

void wypisz_pair(auto &X) {
    for(auto &x : X) cout << x.st << "|" << x.nd << " ";
    cout << "\n";
}

void solve() {
    int n;
    vi A(1, 0);
    vector<signed> PRE(1, 0);
    int ile_1 = 0;//ile trojek o 1 roznym elemencie (wszystkie te same)
    int ile_2 = 0;//ile trojek o 2 roznych elementach
    int ile_123 = 0;//ile trojek o 1, 2 lub 3 roznych elementach
    int ans = 0;

    cin >> n;
    for(int i=1; i<=n; i++) {
        int x;
        cin >> x;
        A.pb(x);
    }

    //return;

    for(int i=1; i<=n; i++) PRE.pb(PRE.back() + A[i]);


    {//Zliczanie ile_123
        //unordered_map<int, int> M;
        #undef int
        vi M(6e7+7, 0);
        int s = signed(3e7 +2);
    
        for(int j1 = n; j1 >= 1; j1--) {
            for(int k1 = 1; k1 <=n; k1++) for(int k2 = k1; k2 <= n; k2++) M[PRE[k2]-PRE[k1-1]+ PRE[j1] + s]++;
            for(int i1 = 1; i1 <= n; i1++) for(int i2 = i1; i2 <= n; i2++) ile_123 += M[-(PRE[i2] - PRE[i1-1] - PRE[j1-1]) + s];
        }
        #define int long long
    }

    //return;

    unordered_map<int, int> M2;
    for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) M2[PRE[j] - PRE[i-1]]++;

    //return;

    {//Zliczanie ile_2
        for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) {
            M2[PRE[j] - PRE[i-1]]--;
            ile_2 += M2[-2*(PRE[j] - PRE[i-1])];
            M2[PRE[j] - PRE[i-1]]++;
        }
        ile_2*=3;
    }

    {//Zliczanie ile_1
        ile_1 = M2[0];
    }

    ans = (ile_123 - ile_2 - ile_1)/6;

    cout << ans << "\n";
}

/*void gen() {
    int n = 500;
    cout << n << "\n";
    for(int i=1; i<=n; i++) cout << (i%2 ? 20000 : -20000) << " ";
}*/

int32_t main() {
    boost
    //gen();
    solve();
}