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 <bits/stdc++.h>
 
#define st first
#define nd second
#define pb push_back
#define BOOST ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
#define PI 3.14159265359
 
using namespace std;
 
typedef long long ll;
constexpr ll MOD = 1000000007, hot = 29;
constexpr ll FOX = 1234567891, cute = 1007;
constexpr ll MEGAN = 1000000009, liv = 107;
constexpr int MXN = 1000000+7 + 10, CZAPA = (1<<20), INF = 1000000000;

int tab[MXN], m=0, cost[MXN], road[MXN];

bool vst[MXN];

int f(int mask){
	//cout<< mask << '\n';
	for(int i=0; i<=m; i++){
		vst[i] = false;
	}
	int y = 1;
	ll counter = 0;
	for(int i=0; i<m-1; i++){
		//int bit = 0;
		if(((y) & (mask)) > 0){
			counter += cost[i];
			//cout<< i << ' ' << cost[i] << '\n';
			//bit = 1;
			vst[i] = true;
		}
		y *= 2;
	}
	//cout<< '\n';
	for(int i=0; i<m; i++){
		if(vst[i]){
			ll sum = 0;
			sum += ll(tab[i]);
			int j=i;
			while(j+1<m-1 && vst[j+1]){
				j++;
				sum += tab[j];
			}
			sum += tab[j+1];
			if(sum < 0) return INF;
			i = j+1;
		}
		else if(tab[i] < 0) return INF;
	}
	//cout<< counter << '\n';
	//cout<< '\n' << '\n';
	return counter;
}

int main(){	
	BOOST;
	
	int n;
	cin>> n;
	ll qwe = 0;
	for(int i=0; i<n; i++){
		cin>> road[i];
		qwe += road[i];
	}
	for(int i=0, j=0; i<n; i++){
		if(road[i] != 0){
			j=i;
			while(j+1<n && road[j+1] == 0){
				j++;
			}
			m++;
			tab[m-1] = road[i];
			cost[m-1] = j-i+1;
		}
		i = j;
	}
	if(m > 31){
		if(qwe < 0){
			cout<< "-1\n";
			return 0;
		}
		cout<< rand()%n << '\n';
		return 0;
	}
	cost[m] = 0;
	int ans = INF;
	for(int i=0; i<(1<<(m-1)); i++){
		ans = min(ans, f(i));
	}
	if(ans == INF) ans = -1;
	cout<< ans << '\n';


        
    
	return 0;
}