using namespace std;
using ll = long long;
using vll = vector<ll>;
int n;
vll psum;
ll solve(void)
{
    if (n < 3 or psum[n] % 3 != 0)
        return 0;
    ll target = psum[n] / 3;
    vll ix[3];
    for (int i = 1; i <= n; ++i)
        for (int k = 1; k <= 3; ++k)
            if (psum[i] == k * target)
                ix[k - 1].push_back(i);
    ll ans = 0;
    for (auto i0 : ix[0])
    {
        auto it1 = upper_bound(ix[1].begin(), ix[1].end(), i0);
        ans += max((ll)distance(it1, ix[1].end()) - (target == 0), 0LL);
    }
    return ans;
}
int main(void)
{
    cin >> n;
    psum.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        cin >> psum[i], psum[i] += psum[i - 1];
    cout << solve() << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using ll = long long;
const int NMAX = 1e5 + 11;
const int MOD = 1e9 + 7;
int n;
bool black[NMAX];
vi g[NMAX];
ll B[NMAX], W[NMAX];
inline ll m(ll x, ll y) { return ((x % MOD) * (y % MOD)) % MOD; }
inline ll p(ll x, ll y) { return ((x % MOD) + (y % MOD)) % MOD; }
void dfs(int u, int parent)
{
    ll bu, wu;
    B[u] = (black[u]);
    W[u] = (!black[u]);
    for (auto v : g[u])
    {
        if (v == parent)
            continue;
        dfs(v, u);
        bu = B[u];
        wu = W[u];
        B[u] = W[u] = 0;
        W[u] = m(W[v], wu);
        B[u] = p(m(bu, W[v]), m(B[v], wu));
        W[u] = p(W[u], m(wu, B[v]));
        B[u] = p(B[u], m(bu, B[v]));
    }
}
int main(void)
{
    int pi, root;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> pi;
        g[pi].push_back(i + 1);
        g[i + 1].push_back(pi);
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> black[i];
        if (black[i])
            root = i;
    }
    dfs(root, -1);
    cout << B[root] << endl;
    return 0;
}

using namespace std;
using ll = long long;
int n;
int a[300010];
ll solve(void)
{
    ll ans = 0;
    ll w = 2;
    sort(a, a + n);
    for (int i = 0; i < n - 1; ++i)
    {
        ans += w * a[i];
        ++w;
    }
    return ans + (w - 1) * a[n - 1];
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << solve() << endl;
    return 0;
}

using namespace std;
map<string, bool> was_already_collected;
int main(void)
{
    int n, counter = 0;
    string tree_kind;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        getline(cin, tree_kind);
        if (not was_already_collected[tree_kind])
            ++counter;
        was_already_collected[tree_kind] = true;
    }
    cout << counter << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using predicate = function<bool(ll)>;
ll n, m, k;
ll n_smaller(ll x)
{
    ll ans = 0;
    for (int row = 1; row <= n; ++row)
        ans += min((x - 1) / row, m);
    return ans;
}
ll bs(ll lo, ll hi, predicate p)
{
    while (lo < hi)
    {
        ll mid = lo + (hi - lo + 1) / 2;
        if (p(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}
int main(void)
{
    cin >> n >> m >> k;
    cout << bs(1, 1e12, [](ll x) { return n_smaller(x) < k; }) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using pqll = priority_queue<ll>;
const ll NMAX = 1e3 + 11;
const ll KMAX = 1e6 + 11;
ll n, m, k, p;
ll rowsum[NMAX], colsum[NMAX];
ll a[KMAX], b[KMAX];
pqll pqrow;
pqll pqcol;
ll solve(void)
{
    ll pleasure(0), maxrow(0), maxcol(0);
    a[0] = b[0] = 0;
    for (int i = 1; i <= k; ++i)
    {
        maxrow = pqrow.top();
        pqrow.pop();
        pqrow.push(maxrow - m * p);
        a[i] = a[i - 1] + maxrow;
        maxcol = pqcol.top();
        pqcol.pop();
        pqcol.push(maxcol - n * p);
        b[i] = b[i - 1] + maxcol;
    }
    pleasure = a[0] + b[k];
    for (ll i = 1; i <= k; ++i)
        pleasure = max(pleasure, a[i] + b[k - i] - (i * (k - i) * p));
    return pleasure;
}
int main(void)
{
    cin >> n >> m >> k >> p;
    ll x;
    for (int row = 0; row < n; ++row)
    {
        for (int col = 0; col < m; ++col)
        {
            cin >> x;
            rowsum[row] += x;
            colsum[col] += x;
        }
    }
    for (int row = 0; row < n; ++row)
        pqrow.push(rowsum[row]);
    for (int col = 0; col < m; ++col)
        pqcol.push(colsum[col]);
    cout << solve() << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
array<ii, 26> dims;
enum ttype
{
    LPAR,
    RPAR,
    MAT,
    END
};
struct Token
{
    ttype type;
    char attr;
};
struct Parser
{
    string input;
    int ix, n;
    Parser(string input) : input(input), ix(0) { n = (int)input.size(); }
    Token get_token(void) const
    {
        if (ix == n)
            return {END, 0};
        else
        {
            char c = input[ix];
            if (isalpha(c))
                return {MAT, c};
            else if (c == '(')
                return {LPAR, c};
            else if (c == ')')
                return {RPAR, c};
            else
                throw -1;
        }
    }
    void eat(ttype t)
    {
        if (t != get_token().type)
            throw -1;
        ++ix;
    }
    inline ll cost(ii a, ii b) { return a.first * a.second * b.second; }
    pair<ii, ll> expr(void)
    {
        Token tkn = get_token();
        if (tkn.type == MAT)
        {
            eat(MAT);
            return {dims[tkn.attr - 'A'], 0};
        }
        else if (tkn.type == LPAR)
        {
            eat(LPAR);
            pair<ii, ll> lmat = expr();
            pair<ii, ll> rmat = expr();
            eat(RPAR);
            if (lmat.first.second == rmat.first.first)
                return {{lmat.first.first, rmat.first.second},
                        lmat.second + rmat.second +
                            cost(lmat.first, rmat.first)};
            else
                throw -1;
        }
        else
            throw -1;
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    while (n--)
    {
        char name;
        int rows, cols;
        cin >> name >> rows >> cols;
        dims[name - 'A'] = {rows, cols};
    }
    string line;
    while (cin >> line)
    {
        try
        {
            Parser p(line);
            cout << p.expr().second << endl;
        }
        catch (int e)
        {
            cout << "error" << endl;
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
using predicate = function<bool(int)>;
int const NMAX = 1e5 + 11;
int n, m, a[NMAX], b[NMAX];
ll cost(int x)
{
    ll ans = 0;
    for (int i = 0; i < n; ++i)
        ans += max(a[i], x) - a[i];
    for (int i = 0; i < m; ++i)
        ans += b[i] - min(b[i], x);
    return ans;
}
int bs(int l, int r, predicate p)
{
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        if (p(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < m; ++i)
        cin >> b[i];
    int x = bs(0, *max_element(b, b + m), [](int x) {
        return (cost(x + 1) - cost(x)) >= 0;
    });
    cout << cost(x) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int ans = 0;
    vi cost(4, 0);
    string s;
    for (auto &x : cost)
        cin >> x;
    cin >> s;
    for (auto c : s)
        ans += cost[c - '0' - 1];
    cout << ans << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, police = 0, ans = 0, event;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> event;
        if (event > 0)
            police += event;
        else if (event == -1 and police > 0)
            --police;
        else
            ++ans;
    }
    cout << ans << endl;
    return 0;
}