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

using namespace std;

typedef long long LL;

const int N = 5e5+5;
const LL INF = 1e18;

vector<LL> in(N);
vector<LL> dp(N);

struct MinTree {
    int base;
    vector<LL> values;

    MinTree(int _base) : base(_base) {
        values.resize(base << 1, INF);
    }

    void update(int x, LL v) {
        x += base;
        values[x] = v;
        while(x != 1) {
            x >>= 1;
            values[x] = min(values[2 * x], values[2 * x + 1]);
        }
    }

    LL query(int a, int b) {
        a += base;
        b += base;
        LL res = min(values[a], values[b]);
        while(a / 2 != b / 2) {
            if((a&1)^1)   res = min(res, values[a+1]);
            if(b&1)   res = min(res, values[b-1]);
            a >>= 1, b >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n;
    cin >> n;
    MinTree tree(1 << 20);
    vector<pair<LL, int>> sums(n+1);

    for(int i = 1;i <= n;++i) {
        cin >> in[i];
        in[i] += in[i-1];
        sums[i] = {in[i], i};
    }

    if(in[n] < 0) {
        cout << "-1\n";
        return 0;
    }

    sort(sums.begin(), sums.end());

    auto it = lower_bound(sums.begin(), sums.end(), pair<LL, int> (0, 0));
    int pos = it - sums.begin(), time = 0;
    tree.update(pos, 0);
    for(int i = 1;i <= n;++i) {
        it = lower_bound(sums.begin(), sums.end(), pair<LL, int> (in[i], i));
        pos = it - sums.begin();

        dp[i] = tree.query(0, pos) + time;
        ++time;
        tree.update(pos, dp[i] - time);
    }

    if(dp[n] == INF)
        cout << "-1\n";
    else {
        cout << dp[n] << "\n";
    }

    return 0;
}