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
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pr(a, b) make_pair(a, b)
const int LIM=5e5+7;
int dp[LIM], ind[LIM], T[3*LIM], N=1;
long long sum[LIM];
vector<pair<long long, int> >V;
void upd(int x, int w) {
	x+=N;
	while(x>1) {
		T[x]=max(T[x], w);
		x/=2;
	}
}
int cnt(int x) {
	x+=N;
	int ans=T[x];
	while(x>1) {
		if(x%2==1) ans=max(ans, T[x-1]);
		x/=2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	rep(i, n) {
		long long a;
		cin >> a;
		sum[i]=sum[max(i-1, 0)]+a;
		if(T[i]>=0) V.push_back(pr(sum[i], i));
	}
	while(N<V.size()) N*=2;
	sort(V.begin(), V.end());
	rep(i, V.size()) ind[V[i].second]=i;
	rep(i, n) if(sum[i]>=0) {
		int p=0, k=V.size()-1;
		while(p<k) {
			int sr=(p+k+1)/2;
			if(V[sr].first>sum[i]) k=sr-1; else p=sr;
		}
		//znajduje najwieksze p, takie ze V[p]<=sum[i]
		dp[i]=cnt(p)+1;
		upd(ind[i], dp[i]);
	}
	if(dp[n-1]) cout << n-dp[n-1]; else cout << -1;
}