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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;

int orginal_table[500006];
int table[500006];
long long sums[500006];
int kinda_result[500006];
long long kinda_sum[5000006];
//int here_ends[500006];
int result=0;
long long sum_result=0;
queue < int > fact;

int bin(int factory, int x, int beg, int en){
    //cout << "beg i en: " << beg << " " << en << endl;
    int mid=(beg+en)/2;
    if(factory==1 && sums[x]>=0)return 1;
    if(beg==en){
        //if(sums[x]-sums[factory]+table[factory])
        if(mid==1)return -1;
        else if(sums[x]-sums[factory]+sums[factory-1]-sums[mid-1]+table[factory]>=0)return mid;
        else return mid-1;
    }

    if(sums[x]-sums[factory]+sums[factory-1]-sums[mid-1]+table[factory]>=0){
        //cout << "kdf" << endl;
        return bin(factory,x,mid+1,en);
    }
    else{
        return bin(factory,x,beg,mid);
    }
    //-result+kinda_result[mid]
}

void change_every(int x,int factory,int best, int best_result){
    table[x]=0;
    if(x-1>=best-best_result)return change_every(x-1,factory,best,best_result);
    else return;
}

void change_every2(int x, int factory, int best, int best_result){
    table[x]=0;
    if(x+1<best)return change_every2(x+1,factory,best,best_result);
    else return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,factory=-1,next_factory=-1,ok=1,MAX=-1;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> table[i];
        orginal_table[i]=table[i];
        if(table[i]<0)fact.push(i);
        sums[i]=sums[i-1]+table[i];
        //if(factory==-1 && table[i]<0)factory=i;
    }
    fact.push(-1);
    factory=fact.front();
    fact.pop();
    while(!fact.empty()){
        //cout << "factory: " << factory << endl;
        /*while(factory<MAX){
            factory=fact.front();
            fact.pop();
        }*/
        if(factory>=MAX){
            int best=-1,best_beg=-1,best_result=n+5;
            for(int i=factory;i<=n;i++){
                //cout << "sprawdzam: " << i << endl;
                /*if(table[i]<0 && i!=factory){
                    //cout << "wychodze " << i << endl;
                    next_factory=i;
                    break;
                }*/
                int bin_result=bin(factory,i,1,factory);
                //cout << "bin_result= " << bin_result << endl;
                if(bin_result!=-1 && i-bin_result-result+kinda_result[bin_result]<best_result){
                    //cout << "licze best_result: " << i << " " << bin_result << " " << result << " " << kinda_result[bin_result] << endl;
                    best_result=i-bin_result-result+kinda_result[bin_result];
                    best=i;
                    best_beg=bin_result;
                }
                //if(i==n)next_factory=i+1;
                //cout << "pauza" << endl;
            }
            MAX=max(MAX,best);
            if(best==-1){
                ok=-1;
                break;
            }
            //cout << "best= " << best << endl;
            //cout << "best_result= " << best_result << endl;
            //int how_change_sum_result=0;
            long long aktualna_suma=0,ile_zmniejszylam=0;
            int czy_tam_bylam=-1;
            for(int i=best_beg;i<best;i++){
                if(i!=best_beg)aktualna_suma+=orginal_table[i];
                else aktualna_suma+=table[i];
                sums[i]=sums[best_beg-1];
                if(aktualna_suma==0){
                    czy_tam_bylam=1;
                    result--;
                    ile_zmniejszylam++;
                }
                if(kinda_result[i]>=ile_zmniejszylam)kinda_result[i]-=ile_zmniejszylam;
            }
            //change_every(factory,factory,best,best_result);
            //change_every2(factory+1,factory,best,best_result);
            for(int i=best;i<=n;i++){
                kinda_result[i]=result+best_result;
            }
            //cout << "sdakfhaslifuakjyjfsa " << best << " " << best_beg << endl;
            for(int i=best-1;i>=best_beg;i--){
                kinda_result[i]=kinda_result[i+1]-1;
            }
            /*for(int i=best-best_result;i<best;i++){
                //how_change_sum_result+=table[i];
                table[i]=0;
                kinda_result[i]=result+i-best+best_result;
                //kinda_sum[i]=sum_result+
            }*/
            table[best]=sums[best]-sums[best-best_result-1];
            //cout << "WYLICZYLAM: " << best_result << endl;
            result+=best_result;
            if(czy_tam_bylam==-1){
                factory=fact.front();
                fact.pop();
            }
            //sum_result-=factory;
        }
        else{
            factory=fact.front();
            fact.pop();
        }
    }
    if(sums[n]<0)cout << -1 << "\n";
    else cout << result << "\n";


    return 0;
}