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 st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int base = (1<<20);
int tree[2*base+1];

void ins(int x, int val) {
	x += base;
	tree[x] = max(tree[x], val);
	x/=2;
	while(x) {
		tree[x] = max(tree[x*2], tree[x*2+1]);
		x/=2;
	}
}
int qry(int l, int r) {
	l+=base, r+=base;
	int res = tree[l]; if(l==r) return res;
	res = max(res, tree[r]);
	while(l/2!=r/2) {
		if(l%2==0) res=max(res, tree[l+1]);
		if(r%2==1) res=max(res, tree[r-1]);
		l/=2;
		r/=2;
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	vector<ll> a(n+1), pref(n+1);
	for(int i=1; i<=n; ++i) cin>>a[i];	
	
	vector<pair<ll, int>> vec;
	for(int i=1; i<=n; ++i) {
		pref[i] = pref[i-1] + a[i];
		if(pref[i]>=0) vec.push_back(mp(pref[i], i));
	}
	if(pref[n]<0) {
		cout<<-1<<'\n';
		return 0;
	}
	sort(vec.begin(), vec.end());
	int nr = 0;
	vector<int> rep(n+1);
	for(int i=0; i<(int)vec.size(); ++i) {
		if(i==0 || vec[i].st != vec[i-1].st) {
			nr++;
		}
		rep[vec[i].nd] = nr;
	}
	for(int i=1; i<n; ++i) {
		if(rep[i]==0) continue;
		int mx = qry(0, rep[i]);	
		ins(rep[i], mx+1); 
	}
	int ans = n-1 - qry(0, rep[n]);
	cout<<ans;	
}