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

using namespace std;

#define N 500100

int n, l, com;
int id[N];
int dp[N];
long long s[N];
vector <int> st;
pair <long long, int> sr[N];

void ins(int x, int w)
{
	x+=com;
	while(x)
	{
		st[x]=min(st[x], w);
		x>>=1;
	}
}

int zap(int a, int b)
{
	a+=com;
	b+=com;
	int ret=1e9;
	while(a<=b)
	{
		if(a&1) ret=min(ret, st[a++]);
		if(!(b&1)) ret=min(ret, st[b--]);
		a>>=1;
		b>>=1;
	}
	return ret;
}

int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; ++i)
	{
		scanf("%lld", &s[i]);
		s[i]+=s[i-1];
		sr[i]={s[i], i};
	}
	sr[n+1]={0, 0};
	sort(sr+1, sr+2+n);
	l=1;
	sr[0]=sr[1];
	for(int i=1; i<=n+1; ++i)
	{
		l+=(sr[i-1].first!=sr[i].first);
		id[sr[i].second]=l;
	}
	com=1;
	while(com<l) com<<=1;
	st.resize(com<<1);
	--com;
	for(int i=com+com+1; i; --i) st[i]=1e9;
	ins(id[0], -1);
	for(int i=1; i<=n; ++i)
	{
		dp[i]=1e9;
		if(s[i]>s[i-1]) dp[i]=dp[i-1];
		dp[i]=min(dp[i], i+zap(1, id[i]));
		ins(id[i], dp[i]-i-1);
	}
	if(dp[n]>n) printf("-1\n");
	else printf("%d\n", dp[n]);
}