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
#include <cstdio>
#include <vector>
#include <map>
#include <limits>
using namespace std;

inline int nextInt() { int n; scanf("%d", &n); return n; }

struct PosValue {
	int pos;
	int value;
};

class Map {
	long long addPower;
	int addCost;
	map<long long, int> data;
public:
	Map() {
		addPower = 0;
		addCost = 0;
	}

	void insert(long long p, int c) {
		p -= addPower;
		c -= addCost;
		if (data.count(p) > 0 && data[p] <= c) return;
		data[p] = c;
		map<long long, int>::iterator it = data.find(p);
		while (it != data.begin()) {
			map<long long, int>::iterator it2 = it;
			--it2;
			if (it2->second < c) break;
			data.erase(it2);
		}
		map<long long, int>::iterator it2 = it;
		++it2;
		if (it2 != data.end() && c >= it2->second)
			data.erase(it);
	}

	void addAll(long long p, int c) {
		addPower += p;
		addCost += c;
	}

	bool containsNonNegativePower() const {
		map<long long, int>::const_iterator it = data.lower_bound(-addPower);
		return it != data.end();
	}

	int getSmallestNonNegativePowerCost() const {
		map<long long, int>::const_iterator it = data.lower_bound(-addPower);
		return it->second + addCost;
	}

	void debug() {
		printf("Map:\n");
		for (map<long long, int>::iterator it = data.begin(); it != data.end(); ++it) {
			printf("%lld => %d\n", it->first + addPower, it->second + addCost);
		}
	}
};

int solve() {
	vector<PosValue> v;
	int n = nextInt();
	for (int pos=1; pos<=n; ++pos) {
		int val = nextInt();
		if (val != 0) v.push_back( {pos, val} );
	}

	if (v.empty()) return 0;

	Map m;
	m.insert(v[0].value, 0);
	//m.debug();

	for (int i=1; i<v.size(); ++i) {
		int prevCost = v[i].pos - v[i-1].pos;
		if (m.containsNonNegativePower()) {
			int cc = m.getSmallestNonNegativePowerCost();
			long long alonePower = v[i].value;
			int aloneCost = cc;
			m.addAll(v[i].value, prevCost);
			m.insert(alonePower, aloneCost);
		} else {
			m.addAll(v[i].value, prevCost);
		}
		//m.debug();
	}
	if (m.containsNonNegativePower())
		return m.getSmallestNonNegativePowerCost();
	return -1;
}

int main() {
	int res = solve();
	printf("%d\n", res);
	return 0;
}