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
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PB push_back
const ll INF = 1e7;
ll wynik[500011];
ll waga[500011];
ll suma[500011];
ll suf_sum[500012];
ll mini = INF;
set<pair<ll, ll>>s;
int n;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i = 1; i <= n; ++i) {
		cin>>waga[i];
		suma[i] = waga[i] + suma[i-1];
	}
	for(int i = n; i >= 1; --i) {
		suf_sum[i] += suf_sum[i+1] + waga[i];
	}
	if(suma[n] < 0) {
		cout<<"-1\n";
		return 0;
	}
	s.insert({0,0});
	for(int i = 1; i <= n; ++i) {
		//cout<<"ROZPATRUJE i: "<<i<<"\n";
		wynik[i] = 2*INF;
		//int current_sum = waga[i];
		if(waga[i] >= 0 && suma[i-1] >= 0) {
			wynik[i] = wynik[i-1];
		}
		/**
		for(int j = i - 1; j > 0; --j) {
			current_sum += waga[j];
			if(suma[j - 1] >= 0 && current_sum >= 0) {
				wynik[i] = min(wynik[i], wynik[j - 1] + i - j);
			}
		}**/
		
		auto iter = s.lower_bound({suf_sum[i+1], -(3*INF)});
		if(iter != s.end()) {
			wynik[i] = min(wynik[i], i + iter->second);
			//cout<<"wybralem wartosc "<<iter->second<<" o sufiksie "<<iter->first<<"\n";
		}
		if(true) {
			pair<ll, ll> to_insert({suf_sum[i], wynik[i-1] - i});
			//cout<<"wkladam "<<to_insert.first<<" "<<to_insert.second<<" dla j "<<i<<"\n";
			auto tz = s.upper_bound(to_insert);
			if(tz != s.end()) {
				if(tz->first > to_insert.first && tz->second <= to_insert.second) {
					//cout<<"kontyna\n";
					continue;
				}
			}
			
			s.insert(to_insert);
			auto x = s.lower_bound({suf_sum[i], -(3*INF)});
			pair<ll, ll> zostaje = (*x);
			auto w_przod = x;
			if(x != s.end())++w_przod;
			vector<pair<ll, ll>> to_erase;
			for(; w_przod != s.end(); ++w_przod) {
				if(zostaje.first == w_przod->first && w_przod->second > zostaje.second) {
					to_erase.PB(*w_przod);
				}
				else {
					break;
				}
			}
			if(x != s.begin()) {
				auto w_tyl = x;
				--w_tyl;
				while(true) {
					if(w_tyl->second >= zostaje.second) {
						to_erase.PB(*w_tyl);
					}else {
						break;
					}
					if(w_tyl == s.begin()) {
						break;
					} else {
						--w_tyl;
					}
				}
			}
			
			for(auto tr : to_erase) {
				s.erase(tr);
			}
		}
		//cout<<"Pokaz set\n";
		//for(auto x : s) { cout<<x.first<<" "<<x.second<<"\n";}
	}/**
	for(int i = 1; i <= n; ++i) {
		cout<<"i: "<<i<<" "<<wynik[i]<<"\n";
	}**/
	cout<<wynik[n]<<"\n";
	return 0;
}