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

constexpr int nax = 5e5;

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    int64_t su = 0;
    set< pair< int64_t, int > > S;
    for (int i = 0; i < n; ++i) {
        //cout << i << ' ';
        //for (auto p : S)
            //cout << '(' << p.first << ' ' << p.second << ')' << ' ';
        //cout << '\n';
        int v; cin >> v;
        su += v;
        if (su < 0) {
            if (i == n - 1)
                return cout << -1 << '\n', 0;
            continue;
        }
        int res = 0;
        auto it = S.upper_bound({su, n});
        if (it != begin(S))
            res = max(res, prev(it)->second);
        if (i == n - 1)
            return cout << (n - 1 - res) << '\n', 0;
        res += 1;
        auto [it2, succ] = S.insert({su, res});
        if (not succ) continue;
        while (next(it2) != end(S) and next(it2)->second <= it2->second)
            S.erase(next(it2));
        if (it2 != begin(S) and prev(it2)->second >= it2->second)
            S.erase(it2);
    }
}