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


#define ll long long
using namespace std;

vector<vector<int>> fapos;
vector<int> fie;
int n; 
ll sum;

vector<int>mem;

pair<int,int> gotoE(int id){
	int reql = fie[id];

	int reqr = fie[id];
	int l = id-1;
	int r = id+1;
	int ld =0;
	int rd = 0;
	while(r<n){	
		reqr += fie[r];
		if(reqr >=0){
			rd = r - id;
			break;
		}
		r++;
	}
	while(l > -1){
		reql += fie[l];
		if(reql>=0){
			ld = id - l;
			break;
		}
		l--;
	}
//	printf("ld: %d \n",ld);
//	printf("rd: %d \n",rd);
	return make_pair(ld, rd);
}

int main(){
	scanf("%d", &n);
	fie.resize(n,0);

	for(int i = 0; i<n;i++){

		scanf("%d ", &fie[i]);
		sum += (ll)fie[i];
		//zapisanie fabryk i zgrupowanie
		if(fie[i] < 0){
			mem.push_back(i);		
		}
		else if(fie[i] > 0){
			if(mem.empty()!= true){
				fapos.push_back(mem);
				mem.clear();
			}	
		}
		if(i == n-1){
			if(mem.empty()!= true){
				fapos.push_back(mem);
			}
		}
		
	}
	if(sum < 0){
		printf("%d\n", -1);
		return 0;
	}

//rozpisanie fabryk
	int minsum = 0;
	for(auto& i : fapos){
		vector<pair<int,int>> possibilities;
		int mini = 10000000;
		for(auto& j : i){
			possibilities.push_back(gotoE(j));

		}
		for(int j  = 0; j<i.size();j++){

			if(j == 0 && possibilities[0].second > 0){
				mini = min(mini, possibilities[j].second);

			}
			else if(j == i.size()-1 && possibilities[j].first> 0){
				mini = min(mini, possibilities[j].first);
			}
			if(possibilities[j].first > 0 && possibilities[j+1].second > 0){
				mini = min(mini, possibilities[j].first+possibilities[j+1].second);
			}
		}

		minsum+=mini;


	}
	printf("%d\n", minsum);


	

}