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
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 5e5 + 10;

vector<pair<int,int>> V;
int streets[MAX];
int tab[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x, sum = 0, res = 0 , sum_power = 0;
    cin >> n;
    V.resize(n + 1000);
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        sum += x;
         V[i] = { x,i };
    }
    if (sum < 0)cout << "-1";
    else
    {
        for (int i = 0; i < n; ++i)
        {
           // cout << "1P" << endl;;
            if (V[i].first < 0)
            {
                //cout << "2P\n" << endl;
                int start = i, end = i, sum_start = 0, sum_end = 0;
                while (sum_start + V[i].first < 0 && start >= 1)
                {
                    //cout << "3P" << endl;
                    sum_start += V[start - 1].first;
                    start = V[start - 1].second;

                }
                while (sum_end + V[i].first < 0 && end <= n-2)
                {
                    //cout << "4P" << endl;
                    sum_end += V[end + 1].first;
                    end = V[end + 1].second;

                }
                //cout << start << " " << sum_start << " " << end << " " << sum_end << endl << endl; 
                while ((V[i].first + sum_start + sum_end - V[start].first >= 0 || V[i].first + sum_start + sum_end - V[end].first >= 0) && (end > 0 && start < n )&&(start != i || end !=i))
                {
                    //cout <<"END  " << V[end].first << "   " << end << endl; 
                    //cout << V[i].first << " " << start << " " << sum_start << " " << V[start].first << " " << end << " " << sum_end << " " << V[end].first << endl;
                    int z = V[i].first + sum_end + sum_start - V[end].first;
                    int p = V[i].first + sum_end + sum_start - V[start].first;
                    //cout << "Z: " << z << "  P: " << p << endl;
                    //cout << "Z1" << endl;
                    bool temp = false;
                    if (p >= 0 && z >= 0)
                    {
                        //cout << "Z2" << endl;
                        //cout << V[i].second << " " << V[start].second << " " << V[end].second << endl;
                        if (V[i].second - V[start].second == V[end].second - V[i].second && p != i && tab[start] > 0)
                        {
                            temp = 1;
                            //cout << "Z4" << endl;
                            sum_end -= V[end].first;
                            end--;
                        }
                        else if (V[i].second - V[start].second >= V[end].second - V[i].second && p != i)
                        {
                            temp = 1;
                            //cout << "Z3" << endl;
                            sum_start -= V[start].first;
                            start++;
                        }
                        else if (z != i) {
                            temp = 1;
                            //cout << "Z4" << endl;
                            sum_end -= V[end].first;
                            end--;
                        }
                    }
                    else if (p >= 0 && start != i)
                    {
                        temp = 1;
                        //cout << "Z5" << endl;
                        sum_start -= V[start].first;
                        start++;
                    }
                    else if (z >= 0 && end != i){
                        temp = 1;
                        ///cout << "Z6" << endl;
                        sum_end -= V[end].first;
                        end--;
                    }
                   // cout << V[i].first << " " << start << " " << sum_start << " " << end << " " << sum_end << endl;
                    if (temp == false) break;
                }
                //cout << endl << start << " " << sum_start << " " << end << " " << sum_end << endl;
                //cout << "        "<<start + 1 << " " << end + 1 << endl;
                V[i].first = sum_start + V[i].first;
                tab[i]++;
                streets[start]++;
                streets[end + 1]--;
            }
            

        }
            for (int i = 0; i < n-1 ; ++i)
            {
                sum_power += streets[i];
                //cout << i + 1 << " " << sum_power << endl;
                if (sum_power > 0 && sum_power+streets[i+1]>0)res++;
            }
            cout << res << endl;
    }
    
    return 0;
}