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
115
116
117
#include<bits/stdc++.h>
using namespace std;
int pocz;
int wejsce[1000010];
long long sumy[1000010];
pair<long long, int> posortowane[1000010];
int kolejnosci[1000010];
long long wynik[1000010];
long long dp[2000010];
struct zas{int p, k;};
zas zakr[2000010];
void ustaw(int n)
{
	int p=1;
	while(p<=n)
		p*=2;
	pocz = p;
	p*=2;
	p--;
	int i=p;
	//printf("p:%d", p);
	while(i>0)
	{
		if(i>p/2)
			zakr[i] = {i,i};
		else
		{
			
			zakr[i] = {zakr[i*2].p, zakr[i*2+1].k};
			//printf("ww:%d ", zakr[i].p);
		}
		i--;
	}
	for(i=1;i<=p;i++)
		dp[i] = -1;
	//for(i=1;i<=p;i++)
	//	printf("z:%d ", zakr[i].p);
}

long long najm(int w,int k)
{
	//printf("w:%d %d %d", w, zakr[w].p, k);
	if(zakr[w].k<=k)
		return dp[w];
	if(zakr[w].p>k)
		return -1;
	long long a, b;
	a = najm(w*2, k);
	b = najm(w*2+1,k);
	if(a != -1 && b != -1)
		return min(a,b);
	return max(a,b);
}

void aktualizuj (int i)
{
	int j = kolejnosci[i] + pocz;
	dp[j] = wynik[i];
	j/=2;
	while(j>0)
	{
		if(dp[j*2]!=-1 && dp[j*2+1]!=-1)
			dp[j] = min(dp[j*2], dp[j*2+1]);
		else
			dp[j] = max(dp[j*2], dp[j*2+1]);
		j/=2;
	}
}

int main()
{
	int n, i;
	scanf("%d", &n);
	ustaw(n);
	for(i=1;i<=n;i++)
	{
		scanf("%d", &wejsce[i]);
		sumy[i] = sumy[i-1]+wejsce[i];
		posortowane[i] = {sumy[i], i};
	}
	sort(posortowane+1, posortowane+n+1);
	for(i=1;i<=n;i++)
		kolejnosci[posortowane[i].second] = i;
	//for(i=1;i<=n;i++)
	//	printf("%d: sum = %lld  kol = %d\n", i, sumy[i], kolejnosci[i]);
	for(i=1;i<=n;i++)
	{
		long long x;
		//sumy[i] - x>0;
		x = kolejnosci[i];
		x = najm(1, pocz + x);
		if(x!=-1)
		{
			//printf("ekstaza ");
			x--;
		}
		
		if(sumy[i]>=0 && x ==-1)
			x = n;
		
		wynik[i] = x;
		
		
		aktualizuj(i);
		//printf("%lld\n", wynik[i]);
	
	}
	for(i=1;i<=n;i++)
		if(wynik[i]>-1)wynik[i]--;
	//printf("\n");
	//for(i=1; i<=n;i++)
	//{
	//	printf("%lld ", wynik[i]);
	//}
	//printf("\n");
	printf("%lld\n", wynik[n]);
}