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

using namespace std;

#define inf 1000000000000000000ll
#define int long long
#define N 500005
#define T (1 << 20)

int n;
int a[N];
int dp[N];
int pf[N];

vector<int> b;

int t[T << 1];
int p[T << 1];

void push(int u) {
    t[u] += p[u];
    if(u < T) {
        p[u << 1 | 0] += p[u];
        p[u << 1 | 1] += p[u];
    }
    p[u] = 0;
}

void add(int l, int r, int v, int x = 0, int y = T, int u = 1) {
    assert(0 <= l && l < r && r <= T);
    push(u);
    if(l >= y || r <= x || v == 0)    return;
    if(l <= x && y <= r) {
        p[u] += v;
        push(u);
        return;
    }
    int m = (x + y) >> 1;
    add(l, r, v, x, m, u << 1 | 0);
    add(l, r, v, m, y, u << 1 | 1);
    t[u] = min(t[u << 1 | 0], t[u << 1 | 1]);
}

int query(int l, int r, int x = 0, int y = T, int u = 1) {
    assert(0 <= l && l < r && r <= T);
    push(u);
    if(l >= y || r <= x)    return LLONG_MAX;
    if(l <= x && y <= r)    return t[u];
    int m = (x + y) >> 1;
    return min(query(l, r, x, m, u << 1 | 0),
               query(l, r, m, y, u << 1 | 1));
}

void update(int pos, int val) {
    add(pos, pos + 1, min(0ll, val - query(pos, pos + 1)));
}

int32_t main() {
    for(int i = 0; i < (T << 1); i++) {
        t[i] = inf;
    }

    scanf("%lld", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", a + i);

        pf[i] = pf[i - 1] + a[i];
        b.push_back(pf[i]);
    }
    b.push_back(0);

    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    auto get_id = [&](int i) {
        return (int)(lower_bound(b.begin(), b.end(), i) - b.begin());
    };

    update(get_id(0), 0);
    for(int i = 1; i <= n; i++) {
        if(a[i] >= 0)   dp[i] = dp[i - 1];
        else            dp[i] = inf;
        
        dp[i] = min(dp[i], query(0, get_id(pf[i]) + 1));
        update(get_id(pf[i]), dp[i] - 1);
        add(0, T, 1);
    }

    // for(int i = 1; i <= n; i++) cerr << dp[i] << ' ';
    // cerr << '\n';

    if(dp[n] >= inf)    puts("-1");
    else                printf("%lld\n", dp[n]);
}