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

const long long inf = 1e15 + 5;
const int N = 5e5 + 5;

int n;
long long tab[N];
int dp[N];
int nr;
int wart[40 * N];
//unordered_map<long long, int> d;
pair<int, int> wsk[40 * N];
long long rozm;
long long wyk = 0;

int create() {
	nr++;
	wart[nr] = 1e9;
	return nr;
}

void insert(long long a, long long pocz, long long kon, long long x, int ile) {
	wyk++;
//	cout << a << " " << pocz << " " << kon << " " << x << endl;
	if (x == 0) exit(0);
//	if (d.find(x) == d.end()) {
//		d[x] = ile;
//	}
//	else {
		wart[x] = min(wart[x], ile);
//	}
	if (pocz == kon) return;
	
	long long sr = (pocz + kon) / 2;
	if (kon <= 0) 	sr--;
	if (a <= sr) {
		if (!wsk[x].first) {
			wsk[x].first = create();
		}
		insert(a, pocz, sr, wsk[x].first, ile);
	}
	else {
		if (!wsk[x].second) {
			wsk[x].second = create();
		}
		insert(a, sr + 1, kon, wsk[x].second, ile);
	}
}

int get(long long a, long long pocz, long long kon, long long x) {
	wyk++;
	int res = 1e9;
	if (a <= pocz) {
		res = min(res, wart[x]);
//			if (ind == 11) {
//				cout << "hej" << pocz << " " << kon << endl;
//			}
		return res;
	}
	if (kon < a) {
		return res;
	}
	long long sr = (pocz + kon) / 2;
	if (kon <= 0) 	sr--;
	if (a <= sr + 1) {
		if (wsk[x].second) {
			res = min(res, wart[wsk[x].second]);
//			if (ind == 11) {
//				cout << "hej2 " << pocz << " " << sr << " " << kon << endl;
//			}
		}
		if (a <= sr && wsk[x].first) {
			res = min(res, get(a, pocz, sr, wsk[x].first));
		}
	}
	else {
		if (wsk[x].second) {
			res = min(res, get(a, sr + 1, kon, wsk[x].second));
		}
	}
	return res;
}
	

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &tab[i]);
//		tab[i] = rand() % 2e5 - 1e5;
	}
	rozm = 1;
	while (rozm < inf)	rozm *= 2;
	long long zero = 0;
//	insert(0, -rozm + 1, rozm, 1, 0);
	create();
	
	for (int i = 1; i <= n; i++) {
//		cout << nr << endl;
		zero -= tab[i];
		tab[i] = zero + tab[i];
//		cout << i << " " << tab[i] << endl;
//		cout << "zero " << zero << endl;
		insert(tab[i], -rozm + 1, rozm, 1, dp[i-1] - (i-1));
		int res = get(zero, -rozm + 1, rozm, 1);
		dp[i] = res + (i - 1);
	}
//	for (int i = 0; i <= n; i++) {
//		printf("%d ", dp[i]);
//	}
	if (dp[n] > 2 * n) {
		dp[n] = -1;
	}
	printf("%d\n", dp[n]);
}