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
110
111
112
113
114
#include <bits/stdc++.h>
#define ll long long

#define debug if(0)

const int MAX_N = 5e5;
const int inf = 2e9;
const int base = 1<<19;

int t[2*base+5];

int n;
ll a[MAX_N+3];
ll p[MAX_N+3];
std::vector<int> ord;
int pos[MAX_N+3];
int dp[MAX_N+3];

void insert(int v, int x) {

	debug std::cout << "Wstawiam " << x << " w punkcie " << v << "\n";
	
	v += base;
	t[v] = x;
	v /= 2;
	while (v > 0) {
		t[v] = std::min(t[v*2], t[v*2+1]);
		v /= 2;
	}
}

int query(int l, int r) {

	debug std::cout << "Pytanie o przedzial [" << l << ", " << r << "]\n";
	
	if (l > r)
		return inf;
	l += base;
	r += base;
	int res = std::min(t[r], t[l]);
	while (l/2 != r/2) {
		if (l % 2 == 0)
			res = std::min(res, t[l+1]);
		if (r % 2 == 1)
			res = std::min(res, t[r-1]);
		l /= 2;
		r /= 2;
	}
	
	debug std::cout << "Wynik to " << res << "\n";
	
	return res;
}

bool cmp1(const int &a, const int &b) {
	if (p[a] < p[b])
		return true;
	else if (p[a] == p[b])
		return a < b;
	return false;
}

void count_dp() {
	if (a[1] >= 0)
		dp[1] = 0;
	else
		dp[1] = inf;
	insert(pos[1], dp[1] - 1);
	for (int i = 2; i <= n; i++) {
		dp[i] = inf;
		int tmp = query(0, pos[i]-1);
		if (a[i] >= 0)
			dp[i] = dp[i-1];
		// byc moze oplaca sie wybudowac droge konczaca sie w i
		if (tmp != inf) 
			dp[i] = std::min(dp[i], tmp + i - 1);
		
		debug std::cout << "dp[" << i << "] = " << dp[i] << "\n";
		if (dp[i] == inf)
			insert(pos[i], inf);
		else
			insert(pos[i], dp[i] - i);
	}
}

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
	std::cin >> n;
	for (int i = 1; i <= n; i++)
		std::cin >> a[i];
	p[0] = 0;
	for (int i = 1; i <= n; i++)
		p[i] = p[i-1] + a[i];
	for (int i = 0; i <= n; i++)
		ord.push_back(i);
	std::sort(ord.begin(), ord.end(), cmp1);
	
	debug {
		std::cout << "Kolejnosc:\n";
		for (auto x: ord)
			std::cout << x << " ";
		std::cout << "\n";
	}
	for (int i = 0; i <= n; i++)
		pos[ord[i]] = i;
	for (int i = 1; i <= n; i++)
		insert(pos[i], inf);
	insert(pos[0], 0);
	count_dp();
	if (dp[n] == inf)
		std::cout << "-1\n";
	else
		std::cout << dp[n] << "\n";
}