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<iostream>
#include<vector>
#include<set>
using namespace std;

struct block
{
    int sume=0;
    int first,second;
};
vector<block> B;
void set_blocks( vector<int> &X )
{
    int n=X.size();
    block x;
  for(int i=1 ; i<n ; i++)
    {
       // cout<<"I "<<i<<endl;
       if(X[i]!=0) 
       {
           x.sume=X[i];
           x.first=i;
           x.second=i;
           B.push_back(x);
       }
    }
}
void repair()
{
    block p;
    int Afirst;
    Afirst=B.size()-1;
    vector<block> P;
    p.first=B[0].first;
    for(int i=0 ; i<B.size()  ; i++)
    {
       // cout<<"I "<<i<<endl;
        //cout<<"first "<<p.first<<endl;
        if(p.sume==0)
        {
        p.first=B[i].first;
        p.sume=B[i].sume;
        }
        else if(p.sume<0) p.sume+=B[i].sume;
        p.second=B[i].second;
        if(p.sume>=0)
        {
           // cout<<"p.first "<<p.first<<" p.second "<<p.second<<" p.sume "<<p.sume<<endl;
            P.push_back(p);
            p.sume=0;
        }
       //  else      cout<<"sume "<<p.sume<<endl;
    }
    if(p.sume!=0)P.push_back(p);
    B=P;
}
void repair_to_left()
{
    //cout<<"TO_LEFT "<<endl;
    block p;
    int Afirst;
    Afirst=B.size()-1;
    vector<block> P;
    for(int i=B.size()-1 ; i>=0  ; i--)
    {
       // cout<<"I "<<i<<endl;
       // cout<<"first "<<p.first<<endl;
        if(p.sume==0)
        {
        p.second=B[i].second;
        p.sume=B[i].sume;
        }
        else if(p.sume<0) p.sume+=B[i].sume;
        p.first=B[i].first;
        if(p.sume>=0)
        {
          //  cout<<"p.first "<<p.first<<" p.second "<<p.second<<" p.sume "<<p.sume<<endl;
            P.push_back(p);
            p.sume=0;
        }
        // else      cout<<"sume "<<p.sume<<endl;
    }
    if(p.sume!=0) P.push_back(p);
    B=P;
}
void repair_block(int n,vector<int> &X )
{
  int l=B[n].first;
  int p=B[n].second;
 // cout<<"l "<<l<<" p "<<p<<endl;
  if(l==p)return;
  while(p>0 &&  X[l]>X[p] && X[p]>=0 && B[n].sume-X[p]>=0) {B[n].second--; B[n].sume-=X[p];p--;} 
  if(l>0 && X[l-1]>X[p] && X[p]>0) {B[n].sume+=X[l-1]-X[p];B[n].second--;l--;p--;B[n].first--;repair_block(n,X) ;};
  while(l<X.size() && X[p]>X[l] && X[l]>=0 && B[n].sume-X[l]>=0) {B[n].first++;B[n].sume-=X[l];l++;}
  if(p<X.size()-1 && X[l]<X[p+1] && X[l]>0) {B[n].sume+=X[p+1]-X[l];B[n].first++;l++;p++;B[n].second++;repair_block(n,X) ;}; 
}
int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    int x;
    vector<pair<int,int> > E,F,W;
    vector<int> X(n+2);
    X[0]=0;
    X[n+1]=0;
    for(int i=1 ; i<=n ; i++)
    {
        cin>>X[i];
        if(X[i]>0) E.push_back({i,x});
        else if(X[i]<0)F.push_back({i,x});
       if(X[i]!=0) W.push_back({i,x});
    }
    set_blocks(X);
    if(B.size()==0) {cout<<0<<endl; return 0;}
   /* for(int i=0 ; i<B.size() ; i++)
    {
        cout<<"BLOCK :"<<i<<endl;
        cout<<B[i].first<<" "<<B[i].second<<" "<<B[i].sume<<endl;
    }*/
    repair();
   /* cout<<"//////////////"<<endl;
    for(int i=0 ; i<B.size() ; i++)
    {
        cout<<"BLOCK :"<<i<<endl;
        cout<<B[i].first<<" "<<B[i].second<<" "<<B[i].sume<<endl;
    }*/
    repair_to_left();
   // cout<<"//////////////"<<endl;
    int result=0;
    bool lose=false;
    for(int i=0 ; i<B.size() ; i++)
    {
            repair_block(i,X);
      //  cout<<"BLOCK :"<<i<<endl;
      //  cout<<B[i].first<<" "<<B[i].second<<" "<<B[i].sume<<endl;
        result+=B[i].second-B[i].first;
        if(B[i].sume<0)lose=true;
    }
    if(!lose)cout<<result<<endl;
    else cout<<-1<<endl;
    return 0;
}