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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int R = 3e6 + 5;

pair <int, pair <int, int> > kraw[N];
long long pref[N];
int b[R];
int e[R];
int czas[R];

int n;
int rozm = 1;
int t = 1;

void insert(int gdzie, int pocz, int kon, int x, int y){
	if(x <= pocz && kon <= y){
		b[gdzie] = x;
		e[gdzie] = y;
		czas[gdzie] = t++;
		return;
	}
	
	int sr = (pocz + kon) / 2;
	if(x <= sr) insert(2 * gdzie, pocz, sr, x, y);
	if(sr < y) insert(2 * gdzie + 1, sr + 1, kon, x, y);
}

pair <pair <int, int>, int> query(int gdzie, int pocz, int kon, int x){
	if(pocz == kon) return make_pair(make_pair(b[gdzie], e[gdzie]), czas[gdzie]);
	
	int sr = (pocz + kon) / 2;
	pair <pair <int, int>, int> w;
	
	if(x <= sr) w = query(2 * gdzie, pocz, sr, x);
	else w = query(2 * gdzie + 1, sr + 1, kon, x);
	
	if(w.second < czas[gdzie]) w = make_pair(make_pair(b[gdzie], e[gdzie]), czas[gdzie]);
	return w;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	
	while(rozm < n) rozm *= 2;

	int ost_ele = 0;
	int p_ele = 0;
	int poz = 0;
	
	for(int i = 1; i <= n; i++){
		long long a;
		cin >> a;
		
		pref[i] = pref[i - 1] + a;
		if(a == 0) continue;
		
		if(ost_ele != 0) kraw[++poz] = make_pair(-(i - ost_ele), make_pair(ost_ele, i));
		else p_ele = i;
		ost_ele = i;
	}
	
	if(pref[n] < 0){
		cout << -1;
		return 0;
	}
	if(p_ele == 0){
		cout << 0;
		return 0;
	}
	
	sort(kraw + 1, kraw + poz + 1);
	insert(1, 1, rozm, p_ele, ost_ele);
	
	int wynik = ost_ele - p_ele;
	//cout << wynik << "\n";
	
	for(int i = 1; i <= poz; i++){
		int odl = -kraw[i].first;
		int a = kraw[i].second.first;
		int b = kraw[i].second.second;
		pair <pair <int, int>, int> pk = query(1, 1, rozm, a);
		if(pref[a] - pref[pk.first.first - 1] >= 0 && pref[pk.first.second] - pref[b - 1] >= 0){
			wynik -= odl;
			insert(1, 1, rozm, pk.first.first, a);
			insert(1, 1, rozm, b, pk.first.second);
			//cout << "TAK " << a << " " << b << " " << odl << "\n";
		}
		/*else{
			cout << "NIE " << a << " " << b << " " << odl << " " << pref[a] - pref[pk.first.first - 1] << " " <<  pref[pk.first.second] - pref[b - 1] << "\n";
		}*/
	}
	
	cout << wynik;
}