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

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

#ifdef LOCAL
ostream &operator<<(ostream &out, string str)
{
    for (char c : str)
        out << c;
    return out;
}
template <class L, class R>
ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.first << ", " << p.second << ")"; }
template <class L, class R, class S>
ostream &operator<<(ostream &out, tuple<L, R, S> p)
{
    auto &[a, b, c] = p;
    return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T>
auto operator<<(ostream &out, T a) -> decltype(a.begin(), out)
{
    out << '{';
    for (auto it = a.begin(); it != a.end(); it = next(it))
        out << (it != a.begin() ? ", " : "") << *it;
    return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts>
void dump(T a, Ts... x)
{
    cerr << a << ", ";
    dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif

main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int Z = 1;
    // cin >> Z;
    while (Z--)
    {
        ll n;
        cin >> n;
        vi V(n);
        for (auto &a : V)
            cin >> a;
        vi S(n + 1, 0);
        for (int i = 0; i < n; i++)
            S[i + 1] = S[i] + V[i];
        vl T(60000001, 0);
        vl C;
        for (int i = 0; i < sz(S); i++)
            for (int j = i + 1; j < sz(S); j++)
            {
                C.push_back(S[j] - S[i]);
                T[-C.back() + T.size() / 2]++;
            }
        ll sum = 0;
        for (int i = 0; i < sz(S); i++)
            for (int j = i + 1; j < sz(S); j++)
                sum -= ll(3) * T[ll(2) * (S[j] - S[i]) + T.size() / 2];
        sum += ll(2) * T[T.size() / 2];
        for (int i = 1; i < sz(S); i++)
        {
            for (auto &a : C)
                sum += T[a + S[i] + T.size() / 2];
            for (auto &a : C)
                T[-a + S[i] + T.size() / 2]++;
        }
        cout << sum / ll(6) << endl;
    }
}