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

struct kr
{
    int lp = 0;
    int rp = 0;
    long long int pow;
};

vector<kr> c;
long long int ans, tmpcost, spozshift, error = 0;
kr tmpkr;
void go(int lk, int poz, int pk, int cost, int pow, int uj)
{
    pow += c[poz].pow;
    if (c[poz].pow < 0) uj++;
    if (pow >= 0 && cost <= tmpcost) {
        tmpcost = cost;
        tmpkr.pow = pow;
        tmpkr.lp = lk;
        tmpkr.rp = pk;
        spozshift = uj;
    }
    if (lk >= 0 && (poz != lk || lk == pk) && (tmpcost > cost+c[poz].lp || c[lk].pow < 0||c[pk-1].pow < 0||c[pk-2].pow < 0)) go(lk-1, lk, pk, cost+c[lk+1].lp, pow, uj);
    if (pk < c.size() && (poz != pk || lk == pk) && (tmpcost > cost+c[poz].rp || c[pk].pow < 0 ||c[pk-1].pow < 0||c[pk-2].pow < 0)) go(lk, pk, pk+1, cost+c[pk-1].rp, pow, uj);
}

int main()
{
    
    int n, poz = 0;
    cin >> n;
    vector<int> spoz;
    for (int i=0; n>i; i++) {
        cin >> ans;
        poz++;
        if (ans != 0) {
            tmpkr.lp = poz;
            tmpkr.pow = ans;
            c.push_back(tmpkr);
            poz = 0;
            if (ans < 0) spoz.push_back(c.size()-1);
        }
        error += ans;
    }
    if (error < 0) cout << "-1\n";
        else {
        for (int i=c.size()-1; i>0; i--) {
            c[i-1].rp = c[i].lp;
        }
        c[0].lp = 0, ans = 0;
        int shift = 0;

        for (int i=0; spoz.size()>i; i++) {
            tmpkr.pow = 0;
            tmpcost = 9223372036854775807;
            spozshift = 0;
            go(spoz[i]-1-shift, spoz[i]-shift, spoz[i]+1-shift, 0, 0, 0);
            c.erase(c.begin()+tmpkr.lp+1, c.begin()+tmpkr.rp-1);
            i += spozshift-1;
            int tmp = tmpkr.lp+1;
            shift += tmpkr.rp-tmpkr.lp-2;
            c[tmpkr.lp+1] = tmpkr;
            if (tmp == 0) c[tmp].lp = 0, c[tmp].rp=c[tmp+1].lp;
            else if (tmp-1 != 0 && tmp == c.size()-1) c[tmp].rp = 0, c[tmp].lp=c[tmp-1].rp;
            else c[tmp].rp=c[tmp+1].lp, c[tmp].lp=c[tmp-1].rp;        
            ans += tmpcost;
        }
        cout << ans << "\n";
    }
    return 0;
}