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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e6;
const int MAXN = 500009;
int offset[MAXN];
int tab[MAXN];
long long pre[MAXN];
int n;
vector<long long> wartosci;
long long mozliwe[MAXN];
int dp[MAXN];
int tmp_i = 0;
const int TREE = 1<<19;
int tree[2*TREE];

void update(int x, int val) {
	x+=TREE;
	tree[x] = min(tree[x], val);
	while(x > 1) {
		x/=2;
		tree[x] = min(tree[x*2], tree[x*2+1]);
	}
}

int query(int l, int r) {
	l+=TREE;
	r+=TREE;
	int result = min(tree[l], tree[r]);
	while(l/2 != r/2) {
		if(l%2==0) 
			result = min(result, tree[l+1]);
		if(r%2==1)
			result = min(result, tree[r-1]);
		l/=2;
		r/=2;
	}
	return result;
}
					

int wez_liczba(long long x) {
	int s = -1;
	int e = tmp_i + 1;
	while(e-s>1) {
		int m = (e+s)/2;
		if(mozliwe[m] <= x)
			s = m;
		else
			e = m;
	}
	return s;
}

int policz() {
	if(pre[1] < 0)
		dp[1] = INF;
	else 
		dp[1] = 0;
	update(wez_liczba(pre[1]), dp[1] + offset[1]);
	for(int i=2;i<=n;i++) {
		int result = INF;
		if(pre[i] >= pre[i-1]) {
			result = min(result, dp[i-1]);
		}
		int liczba = wez_liczba(pre[i]);
		if(pre[i] >= 0) {
			if(liczba != -1) {
				int najlepiej = query(0, liczba);
				result = min(result, najlepiej+i-1);
			}
			result = min(result, i-1);
		}
		update(liczba, result + offset[i]);
		dp[i] = result;
	}
	return dp[n];
}


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

	cin >> n;
	for(int i=0;i<2*TREE;i++)
		tree[i] = INF;
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
		pre[i] = pre[i-1] + tab[i];
		offset[i] = -i;
		wartosci.push_back(pre[i]);
	}
	if(pre[n] < 0) {
		cout << -1 << "\n";
		return 0;
	}
	sort(wartosci.begin(), wartosci.end());
	mozliwe[0] = wartosci[0];
	for(int i=1;i<wartosci.size();i++) {
		if(wartosci[i] != wartosci[i-1]) {
			tmp_i++;
			mozliwe[tmp_i] = wartosci[i];
		}
	}
	int wynik = policz();	
	cout << wynik << "\n";
}