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
118
119
120
121
122
123
124
125
#include <cstdio>
#include <algorithm>
using namespace std;

#define LL long long
#define MAXI 1000000000000000LL

struct node {
	node *left, *right;
	int result;
	node(){
		left = nullptr;
		right = nullptr;
		result = 1000000;
	}
};

node* root = new node();

void add_tree(node* pos, LL s, LL cs, LL ce, int val){
	if ((s == cs) && (s == ce)){
		pos->result = min(pos->result, val);
		return;
	}
	else if (s <= (cs + ce)/2){
		if (pos->left == nullptr){
			pos->left = new node();
		}
		add_tree(pos->left, s, cs, (cs + ce)/2, val);
	}
	else if (s > (cs + ce)/2){
		if (pos->right == nullptr){
			pos->right = new node();
		}
		add_tree(pos->right, s, (cs + ce)/2 + 1, ce, val);
	}
	if ((pos->left != nullptr) && (pos->right != nullptr)){
		pos->result = min(pos->left->result, pos->right->result);
	}
	else if (pos->left != nullptr){
		pos->result = pos->left->result;
	}
	else {
		pos->result = pos->right->result;
	}
}

int get_tree(node* pos, LL s, LL e, LL cs, LL ce){
	int def = 1000000;
	if ((s == cs) && (e == ce)){
		if (pos == nullptr){
			return def;
		}
		else {
			return pos->result;
		}
	}
	else if ((s <= (cs + ce)/2) && (e <= (cs + ce)/2)){
		if (pos->left != nullptr){
			return get_tree(pos->left, s, e, cs, (cs + ce)/2);
		}
		else {
			return def;
		}
	}
	else if ((s > (cs + ce)/2) && (e > (cs + ce)/2)){
		if (pos->right != nullptr){
			return get_tree(pos->right, s, e, (cs + ce)/2 + 1, ce);
		}
		else {
			return def;
		}
	}
	else {
		int r = def;
		if (pos->left != nullptr){
			r = min(r, get_tree(pos->left, s, (cs + ce)/2, cs, (cs + ce)/2));
		}
		if (pos->right != nullptr){
			r = min(r, get_tree(pos->right, (cs + ce)/2 + 1, e, (cs + ce)/2+1, ce));
		}
		return r;
	}
}

int t[500005], n;

int main(){
	scanf("%d", &n);
	LL tmp = 0;
	for (int i = 1; i <= n; i++){
		scanf("%d", &t[i]);
		tmp += t[i];
	}
	if (tmp < 0){
		printf("-1\n");
		return 0;
	}
	add_tree(root, 0, 0, MAXI, 0);
	int lr = 0;
	LL s = 0;
	for (int i = 1; i <= n; i++){
		if (s >= 0){
			add_tree(root, s, 0, MAXI, lr - i);
		}
		if (t[i] < 0){
			if (s + t[i] >= 0){
				lr = get_tree(root, 0, s + t[i], 0, MAXI) + i;
			}
		}
		else {
			if (s + t[i] >= 0){
				int w = get_tree(root, 0, s + t[i], 0, MAXI);
				lr = min(1000000, min(w + i, lr));
				//printf("aa %d %d\n", i, lr);
			}
		}
		s += t[i];
		if (s < 0){
			//printf("bebe %d\n", i);
			lr = 1000000;
		}
	}
	printf("%d\n", lr);
}