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
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " " << x << endl;

// #define int long long // uważaj

const int N = 500005;
const int base = (1 << 19);

long long pref[N];
int tree[2 * base + 5];

void insert(int v, int w) {
    v += base;
    tree[v] = w;
    v /= 2;

    while(v) {
        tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        v /= 2;
    }

}

int query(int l, int r) {
    assert(l <= r);

    l = l + base - 1;
    r = r + base + 1;
    int w = 0;

    while(l + 1 < r) {
        if(l % 2 == 0) w = max(w, tree[l + 1]);
        if(r % 2 == 1) w = max(w, tree[r - 1]);
        l /= 2;
        r /= 2;
    }

    return w;
}

void solve() {
    int n;
    cin >> n;

    vector <long long> vek;
    vek.push_back(0);

    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        pref[i] = pref[i - 1] + a;
        if(pref[i] >= 0) vek.push_back(pref[i]);
    }

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

    sort(vek.begin(), vek.end());
    vek.resize(unique(vek.begin(), vek.end()) - vek.begin());

    for(int i = 1; i <= n; i++) {
        if(pref[i] < 0) continue;
        pref[i] = upper_bound(vek.begin(), vek.end(), pref[i]) - vek.begin() - 1;
    }

    int ans = 0;

    for(int i = 1; i <= n; i++) {
        if(pref[i] < 0) continue;
        ans = query(0, pref[i]) + 1;
        insert(pref[i], ans);
    }

    cout << n - ans << "\n";
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test = 1;

	while(test--){
		solve();
	}

	return 0;
}