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
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define int long long
using namespace std;
vector<int> v;
int n, tab[500009], sumy[500009], wer[500009], cur, lwkoniec, prkoniec, wynik, ile, a, b;
int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>tab[i];
		cur+=tab[i];
		sumy[i]=cur;
		if(tab[i]<0)
			v.pb(i);
	}
	if(cur<0){
		cout<<"-1\n";
		return 0;
	}
	else{
		for(int poz:v){
			if(poz>prkoniec){
			//for(int i=1; i<=n; i++)
			//	cout<<tab[i]<<"\t";
			//cout<<"\n";
			bool git=false;
			for(int i=1; i<=n && git==false; i++){
				for(int j=0; j<=i && git==false; j++){
					a=max(poz-i+j, 1LL);
					b=min(poz+j, n);
					//cout<<poz<<" "<<a<<" "<<b<<" suma "<<sumy[b]-sumy[a-1]<<"\n";
					if(sumy[b]-sumy[a-1]>=0){
						
						if(a<=prkoniec){
							int ile=0;
							for(int q=a; q<prkoniec; q++)
								ile+=!wer[q];
							if(ile==0){
								wynik+=b-prkoniec;
							}
							else{
								wynik+=(b-a+ile)/2;
							}
							
						}
						else
							wynik+=b-a;
						for(int q=a; q<b; q++){
							tab[q]=0;
							wer[q]=0;
						}
						tab[b]=sumy[b]-sumy[a-1];
						wer[b]=1;
						for(int q=a; q<=n; q++)
							sumy[q]=sumy[q-1]+tab[q];
						git=true;
						prkoniec=b;
					}
				}
			}
			//cout<<wynik<<"\n";
			}
		}
	}
	cout<<wynik<<"\n";
	return 0;
}