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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;

const int tree_base = 1 << 3;//19
long long pre_tree[2][tree_base*2];

vector <pair<long long, long long>> v;

int temp;

long long sum = 0;

priority_queue <pair<long long, long long>> q;

void update_tree(int a, int b,long long c, int p) {
	a += tree_base;
	b += tree_base;

	while (a < b) {
		if (a % 2 == 1) {
			pre_tree[p][a] += c;
			a++;
		}
		if (b % 2 == 0) {
			pre_tree[p][b] += c;
			b--;
		}
		a /= 2;
		b /= 2;
	}
	if (a == b) {
		pre_tree[p][a] += c;
	}
	return;
}


long long read_tree(int a, int p) {
	a += tree_base;
	long long ret = 0;
	while (a > 0) {
		ret += pre_tree[p][a];
		a /= 2;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	int len = 1;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		if (temp == 0) {
			len++;
		}
		else {
			if (v.size() != 0) {
				v[v.size() - 1].second = len;
				sum += len;
				len = 1;
			}
			v.push_back({ temp,0 });
		}
	}
	
	for (int i = 0; i < v.size(); i++) {
		if (i != 0) {
			pre_tree[0][i + tree_base] = pre_tree[0][i + tree_base - 1];
		}
		pre_tree[0][i + tree_base] += v[i].first;
	}

	for (int i = v.size() - 1; i >= 0; i--) {
		if (i != v.size() - 1) {
			pre_tree[1][i + tree_base] = pre_tree[1][i + tree_base + 1];
		}
		pre_tree[1][i + tree_base] += v[i].first;
	}

	if (pre_tree[0][0 + tree_base] < 0) {
		cout <<-1;
		return 0;
	}

	if (n == 1) {
		cout << 0;
		return 0;
	}

	for (int i = 0; i < v.size()-1; i++) {
		if (read_tree(i, 0) >= 0 && read_tree(i + 1, 1) >= 0) {
			q.push({ v[i].second,i });
		}
	}

	while (!q.empty()) {
		if (read_tree(q.top().second, 0) >= 0 && read_tree(q.top().first + 1, 1) >= 0) {
			sum -= q.top().first;
			update_tree(0, q.top().second, -1 * read_tree(q.top().second + 1, 1), 1);
			update_tree(q.top().second + 1, v.size() - 1, -1 * read_tree(q.top().second, 0), 0);
		}
		q.pop();
	}
	cout << sum;

	return 0;
}