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
#include<iostream>
#include<algorithm>

using namespace std;

const int MAX_N = 500007;
const int DEPTH = 19;
const int LEAVES = 1 << DEPTH;

inline int L(int v) {return (v << 1);}
inline int R(int v) {return ((v << 1)|1);}
inline int P(int v) {return (v >> 1);}

int tree[2 << DEPTH];

int query(int s, int e, int vs, int ve, int v) {
	if(e < vs || ve < s) return 1e9;
	if(s <= vs && ve <= e) return tree[v];
	int split = (vs+ve)>>1;
	return min(query(s, e, vs, split, L(v)), query(s, e, split+1, ve, R(v)));
}

inline int query(int s, int e) {
	return query(s, e, 0, LEAVES-1, 1);
}

void change(int v, int val) {
	v |= LEAVES;
	tree[v] = val;
	v = P(v);
	while(v > 0) {
		tree[v] = min(tree[L(v)], tree[R(v)]);
		v = P(v);
	}
}

int scaled[MAX_N];
pair<long long, int> temp[MAX_N];
int dp[MAX_N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, fab = -1;
	cin >> n;
	temp[0] = make_pair(0, 0);
	for(int i = 1; i <= n; i++) {
		cin >> temp[i].first;
		if(fab == -1 && temp[i].first < 0) {
			fab = i;
		}
		temp[i].first += temp[i-1].first;
		temp[i].second = i;
	}
	if(fab == -1) {
		cout << "0\n";
		return 0;
	}
	if(temp[n].first < 0) {
		cout << "-1\n";
		return 0;
	}
	sort(temp, temp+n+1);
	int a = 0;
	scaled[temp[0].second] = 0;
	for(int i = 1; i <= n; i++) {
		if(temp[i-1].first < temp[i].first) a++;
		scaled[temp[i].second] = a;
	}
	for(int i = 0; i < LEAVES; i++) {
		tree[i|LEAVES] = 1e9;
	}
	tree[scaled[n]|LEAVES] = n;
	for(int i = LEAVES-1; i > 0; i--) {
		tree[i] = min(tree[L(i)], tree[R(i)]);
	}
	for(int i = n; i >= 1; i--) {
		dp[i] = query(scaled[i-1], a)-i;
		if(tree[scaled[i-1]|LEAVES] > dp[i]) change(scaled[i-1], dp[i]+i-1);
	}
	int best = 1e9;
	for(int i = 1; i <= fab; i++) {
		best = min(best, dp[i]);
	}
	cout << best << '\n';
	return 0;
}