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
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

struct CT {
	int i, g, c;
	long long s;
};

int N;
vector<CT> cti;
map<long long, int> se;

void show_se() {
	printf("D: EMAP (nadmiar->koszt) BEGIN:\n");
	for (auto it = se.begin(); it != se.end(); it++) {
		printf("D: %lld -> %d\n", it->first, it->second);
	}
	printf("D: EMAP END.\n");
}

void s(int i) {
	auto it = se.upper_bound(cti[i].s);
	if (it != se.begin()) {
		it--;
		cti[i].c = cti[i].i - it->second;
	}

	it = se.lower_bound(cti[i].s);
	auto it2 = it;
	while (it2 != se.end() && it2->second <= cti[i].i + cti[i].g - cti[i].c) {
		it2++;
	}
	se.erase(it, it2);

	se[cti[i].s] = cti[i].i + cti[i].g - cti[i].c;
}

int main() {
	int A, p, b;
	long long d = 0LL;

	scanf("%d", &N);
	cti.resize(N);

	p = b = 0;
	for (int i = 0; i < N; ++i) {
		scanf("%d", &A);
		if (A != 0) {
			d += A;
			cti[p++] = { i - b, 1, i - b, d };
		} else if (p > 0) {
			cti[p - 1].g++;
		} else {
			b++;
		}
	}

	if (d < 0) {
		printf("-1\n");
		return 0;
	}

	N = p;
	for (int i = 0; i < N; ++i) {
		if (cti[i].s >= 0) {
			s(i);
		}
	}

	printf("%d\n", cti[N - 1].c);
	return 0;
}