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
#include <iostream>
#include <unordered_map>
#include <algorithm>

const int64_t NN = 1ll<<21;
const int MAXN = 500005;
const int64_t INF = 1000000000000000000ll;

int64_t E[MAXN];
int64_t EE[MAXN];
int64_t S[MAXN];
int64_t S2[MAXN];
int64_t B[MAXN];
int n;

struct InfInt {
    int64_t v;
    InfInt() : v(INF) {}
    InfInt(int64_t v) : v(v) {}
    operator int64_t() const { return v; }
    int64_t& val() { return v; }
};

class RT {
public:
    RT() {
    }
    void set(int64_t pos, int64_t val) {
        pos += NN;
        while (pos > 0) {
            auto& v = V[pos];
            v.val() = std::min(v.val(), val);
            pos /= 2;
        }
    }
    int64_t min(int64_t l, int64_t r) {
        l += NN;
        r += NN;
        int64_t vl = V[l];
        int64_t vr = V[r];
        while (l/2 < r/2) {
            if (!(l&1)) vl = std::min(vl, V[l+1].val());
            if (r&1) vr = std::min(vr, V[r-1].val());
            l/=2;
            r/=2;
        }
        return std::min(vl, vr);
    }
    //std::unordered_map<int64_t, InfInt> V;
    InfInt V[NN*2];
} rt;

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin >> n;
    for (int i=1;i<=n;++i) std::cin >> E[i];
    for (int i=1;i<=n;++i) EE[i] = EE[i-1] + (E[i] < 0 ? E[i] : 0);
    // for (int i=1;i<=n;++i) S[i] = S[i-1] + E[i];
    for (int i=n;i>0;--i) S[i] = S[i+1] + E[i];
    for (int i=1;i<=n;++i) S2[i] = S[i];
    std::sort(S2+1, S2+n+2);
    std::unordered_map<int64_t, int64_t> SS;
    for (int i=1;i<=n+1;++i) SS[S2[i]] = i;
    for (int i=1;i<=n+1;++i) S[i] = SS[S[i]];

    // for (int i=1;i<=n;++i) std::clog << S[i] << " ";
    // std::clog << std::endl;
    B[0] = 0;
    rt.set(S[1], n);
    for (int i=1;i<=n;++i) {
        // B[i] = EE[i] < 0 ? INF : 0;
        B[i] = INF;
        if (E[i] >= 0) B[i] = B[i-1];
        // // std::clog << i << " $$$$$$$$$$$" << std::endl;
        // for (int j=0;j<=i;++j) {
        //     if (S[i]-S[j] >= 0) {
        //         // int64_t cost = EE[i]-EE[j] < 0 ? i-j-1 : 0;
        //         int64_t cost = std::max(i-j-1, 0);
        //         B[i] = std::min(B[i], cost + B[j]);
        //         // std::clog << "*  " << j << "  " << B[i] << " vs " << cost << " + " << B[j] << std::endl;
        //     }
        // }
        // // std::clog << i << " " << B[i] << std::endl;

        // 3 1 6 6 4 4 4 4 0 0 0 1 -3 -3 -3 -3 -3 
        int steps = n-i;
        // std::clog << S[i+1] << " " << steps << std::endl;
        // for (int s=-5;s<6;++s) std::clog << " $ " << s << " = " << rt.min(s, s)-steps-1 << std::endl;
        // std::clog << std::endl;
        B[i] = std::min(rt.min(S[i+1], NN/2) - steps-1, B[i]);
        rt.set(S[i+1], B[i]+steps);
        
        // std::clog << "# " << i << " " << B[i] << std::endl;
    }
    if (B[n] < INF/2) std::cout << B[n] << std::endl;
    else std::cout << -1 << std::endl;
    return 0;
}