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
#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "()" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
    o << "{";int i = 0;
    for(auto e : x) o << ", "+!i++<<e;
    return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;
 
constexpr int N = 20000 * 500 + 1;
int cn[2][N];

void test() {
    int n; cin>>n;
    vector <int> v(n);
    vector <int> ps(n+1);

    for (int i=0; i<n; ++i) {
        cin>>v[i];
        ps[i+1] = ps[i] + v[i];
    }

    for (int i=1; i<=n; ++i) {
        for (int j=i; j<=n; ++j) {
            int s = ps[j] - ps[i-1];
            cn[s >= 0][abs(s)]++;
        }
    }

    vector <pii> el;
    for (int j=0; j<2; ++j) {
        for (int i=0; i<N; ++i) {
            if (cn[j][i]) {
                el.push_back({cn[j][i], (j ? i : -i)});
            }   
        }
    }

    long long res = 0;
    
    for (int i=0; i<el.size(); ++i) {
        const ll c1 = el[i].fi;
        int e1 = el[i].se;
        for (int j=i+1; j<el.size(); ++j) {
            const int e2 = el[j].se;
            const int e3 = - e1 - e2;

            if (e1 == e2 || e1 == e3 || e2 == e3 || e3 >= N) {
                continue;
            }

            const ll c2 = el[j].fi;
            const ll c3 = cn[e3 >= 0][abs(e3)];

            long long add = c1*c2*c3;

            res += (c1 * c2 * c3);
        }
    }
    res /= 3ll;

    for (int i=0; i<el.size(); ++i) {

        const int e3 = -el[i].se * 2;
        if (el[i].se == 0 || e3 >= N) continue;

        const ll c1 = el[i].fi;
        const ll c3 = cn[e3 >=0][abs(e3)];

        res += c3 * (c1 * (c1-1))/2ll;
    }

    long long zcnt = cn[1][0];
    res += ((zcnt-2)*(zcnt-1)*zcnt)/6ll; // dodać wszystkie trójki z zer 

    cout<<res<<'\n';
}
 
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t = 1; 
  while (t--) {
    test();
  }
}