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

using namespace std;
typedef long long ll;
const int N = 1<<20;
map<ll, int> mapa;
ll tab[N];
int drz[2 * N];
int w[N];

void Dodaj(int v, int il)
{
	v += N;
	while(v > 0)
	{
		drz[v] = min(drz[v], il);
		v /= 2;
	}
}

int MinNaPrzedz(int a, int b)
{
	a += N;
	b += N;
	int w;
	w = min(drz[a], drz[b]);
	while(a / 2 != b / 2)
	{
		if(a % 2 == 0)
			w = min(w, drz[a + 1]);
		if(b % 2 == 1)
			w = min(w, drz[b - 1]);
		a /= 2;
		b /= 2;
	}
	return w;
}

void DP(int n)
{
	int i;
	ll s;
	s = 0LL;
	for(i = 1; i < 2 * N; ++i)
	{
		drz[i] = 5 * n;
	}
	Dodaj(mapa[0LL], -1);
	for(i = 1; i <= n; ++i)
	{
		s += tab[i];
		w[i] = MinNaPrzedz(0LL, mapa[s]) + i;
		Dodaj(mapa[s], w[i] - i - 1);
	}
	if(s < 0)
		cout << -1 << "\n";
	else
		cout << w[n] << "\n";
}

void Wczytaj(int &n)
{
	int i;
	ll s;
	vector<ll> c;
	c.push_back(0LL);
	s = 0LL;
	cin >> n;
	for(i = 1; i <= n; ++i)
	{
		cin >> tab[i];
		s += tab[i];
		c.push_back(s);
	}
	sort(c.begin(), c.end());
	for(i = 0; i <= n; ++i)
	{
		if(i == 0 || c[i] != c[i - 1])
			mapa[c[i]] = i + 1;
	}
}

void Elektrownia()
{
	int n;
	Wczytaj(n);
	DP(n);
}

int main ()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Elektrownia();
	
	return 0;
}