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
#include<bits/stdc++.h>
using namespace std;
int n;
int energy[500000+69];
long long pref[500000+69];
int after[500000+69];
int tree[(2<<20)+69];
int arr[500000+69];
int mapa[500000+69];
bool cmp(int a,int b){
	return (pref[n]-pref[after[a+1]-1]>pref[n]-pref[after[b+1]-1]);
}
int mnp(int v,int mp,int mk,int p,int k){
	if(p<=mp && mk<=k)
		return tree[v];
	if(mk<p || k<mp)
		return 1000000000+69;
	return min(mnp(v*2,mp,(mp+mk)/2,p,k),mnp(v*2+1,(mp+mk+1)/2,mk,p,k));
}
int main(){
	int m,i,r,v,pom,p,k,s,ost,pie;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&energy[i]);
	i=n;
	while(energy[i]==0 && i>0)
		i--;
	if(i==0){
		printf("0\n");
		return 0;
	}
	after[i]=i;
	ost=i;
	pie=i;
	i--;
	while(i>=0){
		after[i]=after[i+1];
		if(energy[i]!=0){
			after[i]=i;
			pie=i;
		}
		i--;
	}
	for(i=1;i<=n;i++)
		pref[i]=pref[i-1]+energy[i];
	m=1;
	arr[0]=0;
	for(i=1;i<=n;i++)
		if(energy[i]!=0 && pref[i]>=0 && pref[n]-pref[after[i+1]-1]>=0)
			arr[m++]=i;
	if(pref[n]<0){
		printf("-1\n");
		return 0;
	}
	m--;
	sort(arr,arr+m,cmp);
	for(i=0;i<m;i++)
		mapa[arr[i]]=i;
	r=1;
	while(r<m)
		r*=2;
	for(i=0;i<r;i++)
		tree[r+i]=1000000000+69;
	for(i=r-1;i>=1;i--)
		tree[i]=1000000000+69;
	tree[r+mapa[0]]=n-1;
	v=(r+mapa[0])/2;
	while(v>0){
		tree[v]=min(tree[2*v],tree[2*v+1]);
		v/=2;
	}
	//printf("ost: %d\n",ost);
	for(i=1;i<ost;i++)
		if(energy[i]!=0 && pref[i]>=0 && pref[n]-pref[after[i+1]-1]>=0){
			p=0;
			k=m-1;
			while(p<k){
				s=(p+k+1)/2;
				//printf("i: %d p: %d k: %d s: %d\n",i,p,k,s);
				if(pref[i]-pref[after[arr[s]+1]-1]>=0)
					p=s;
				else
					k=s-1;
			}
			//printf("binsearch: %d arr: %d\n",p,arr[p]);
			s=p;
			if(pref[i]-pref[after[arr[s]+1]-1]>=0){
				//printf("ok\n");
				pom=mnp(1,0,r-1,0,s);
				//printf("pom: %d tree: %d %d %d %d %d %d %d %d\n",pom,tree[r],tree[r+1],tree[r+2],tree[r+3],tree[r+4],tree[r+5],tree[r+6],tree[r+7]);
				tree[r+mapa[i]]=pom-(after[i+1]-i);
				//printf("tree[%d]:=%d\n",mapa[i],pom-(after[i+1]-i));
				v=(r+mapa[i])/2;
				while(v>0){
					tree[v]=min(tree[2*v],tree[2*v+1]);
					v/=2;
				}
			}
		}
	//for(i=0;i<m;i++)
		//printf("i: %d pos: %d cost: %d\n",i,arr[i].pos,arr[i].cost);
	printf("%d\n",tree[1]-(n-ost)-(pie-1));
	return 0;
}