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
#include <bits/stdc++.h>
#define ff first
#define ss second
const int N=500000;
const int S=524288;
const long long INF=1000000000000000;

using namespace std;

int n,c;
map <long long,int> m;
long long a[N+1],d,t[2*S],w;

long long query(int p, int q) {
	p+=S; q+=S;
	long long w=min(t[p],t[q]);
	while (p/2!=q/2) {
		if (p%2==0) w=min(w,t[p+1]);
		if (q%2==1) w=min(w,t[q-1]);
		p/=2; q/=2;
	}
	return w;
}

void update(int p, long long a) {
	p+=S;
	t[p]=a;
	while (p>1) {
		p/=2;
		t[p]=min(t[2*p],t[2*p+1]);
	}
}

int main() {
	scanf("%d",&n);
	for (int i=0; i<2*S; i++) t[i]=INF;
	m[0]=0;
	for (int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
		m[a[i]]=0;
	}
	c=0; for (auto i: m) m[i.ff]=c++;

	update(m[0],0);

	for (int i=1; i<=n; i++) {
		w=query(0,m[a[i]]);
		if (w!=INF) {
			w+=(long long)(i-1);
			update(m[a[i]],w-(long long)i);
		}
	}

	printf("%lld\n",w==INF?-1:w);
	return 0;
}