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

using namespace std;

bool comp(const pair<int,int>&a,const pair<int,int>&b){
    return a.second-a.first>b.second-b.first;
}

int main(){
    set<int>beg;
    vector<long long int>pref(1,0);
    vector<int>build;
    vector<pair<int,int>>road;
    int n,b,e,wyn=0;
    long long int a;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        pref.push_back(pref.back()+a);
        if(a!=0)build.push_back(i);
    }
    if(pref.back()>=0){
        for(unsigned int i=1;i<build.size();i++)road.push_back(make_pair(build[i-1],build[i]));
        sort(road.begin(),road.end(),comp);
        beg.insert(0);
        beg.insert(n);
        for(unsigned int i=0;i<road.size();i++){
            b=*(--beg.upper_bound(road[i].first));
            e=*beg.lower_bound(road[i].second)-1;
            if(pref[road[i].first+1]-pref[b]>=0&&pref[e+1]-pref[road[i].second]>=0){
                wyn+=road[i].second-road[i].first;
                beg.insert(road[i].second);
            }
        }
        cout << n-wyn-1<< endl;
    }
    else cout << "-1" << endl;
}