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

#define FOR(i,be,en) for(int i=be; i<en; i++)

using namespace std;
typedef long long ll;
const int MAXN=5e5+5, B=(1<<19), INF=1e9;

int dp[MAXN];
ll S[MAXN];
int U[MAXN];

inline int Sum(int a, int b){
	return S[b]-S[a-1];
}

inline int Neg(int a, int b){
	return (U[b]-U[a-1]);
}

int Cost(int i, int j){
	if(Sum(i,j)<0) return INF;
	if(!Neg(i,j)) return 0;
	int d=i, g=j;
	while(d+1<g){
		int s=((d+g)>>1);
		if(Neg(i,s-1)<=0 && Sum(s,j)>=0) d=s;
		else g=s;
	}
	return j-d;
}

int TotalCost(int n){
	FOR(i,1,n+1) dp[i]=INF;
	if(S[1]>=0) dp[1]=0;
	FOR(i,1,n+1){
		FOR(j,1,i){
			dp[i]=min(dp[i], dp[j]+Cost(j+1,i));
		}
	}
	if(dp[n]==INF) dp[n]=-1;
	return dp[n];
}

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

	int n;
	cin>>n;

	FOR(i,1,n+1){
		int a;
		cin>>a;
		S[i]=(S[i-1]+1LL*a);
		U[i]=U[i-1];
		if(a<0) U[i]++;
	}

	cout<<TotalCost(n);


	return 0;
}