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
#include<cstdio>
#include<algorithm>
#include<vector>
#define S 500007
#define M 524288

using namespace std;
typedef long long ll;

ll pref[S];

vector < pair < ll, int > > V;

int tree[2*M+7];

int maxx(int l, int r, int ll, int rr, int w){
    if (l > rr || r < ll)
        return 0;
    if(l >= ll && r <= rr){
        return tree[w];
    }
    int sr = (l+r)/2;
    return max(maxx(l,sr,ll,rr,w*2),maxx(sr+1,r,ll,rr,w*2+1));
}

int main(void){
    int n;
    scanf("%d",&n);
    ll x;
    for(int i = 1; i <= n;i++){
        scanf("%lld",&x);
        pref[i] = pref[i-1] + x;
        V.push_back({pref[i],i});
    }
    if(pref[n] < 0){
        printf("-1");
        return 0;
    }
    sort(V.begin(),V.end());
    int y;
    for(int i = 1; i <= n;i++){
        x = V[i-1].first;
        y = V[i-1].second;
        if(x >= 0){
            int p = maxx(1,M,1,y,1);
            int w = y+M-1;
            tree[w] = p+1;
            while(w != 1){
                w/= 2;
                tree[w] = max(tree[w*2],tree[w*2+1]);
            }
        }
    }
    printf("%d",n-maxx(1,M,n,n,1));
    return 0;
}