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
#include <stdio.h>
#include <strings.h>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <bits/stdc++.h>
#include <tuple>
#include <cstdio>

using namespace std;

typedef unsigned long long ullong;


int main() {
    int n, v;
    scanf("%d\n", &n);
    
    vector< tuple<int,int> > cities; // (positon, value)
    map<int, unsigned int> pos2con; //for the city
    map<int, unsigned int> pos2pro; //for the city
    map<int, ullong> pos2procum;  //total pro so far 
    map<int, ullong> pos2concum;  //total con so far
    ullong con_total=0;
    ullong pro_total=0;
    for (int i=0; i<n; ++i){
        scanf("%d", &v);
        if (v==0) continue;
        if (v>0) { 
            pro_total += abs(v);
            pos2pro[i] = abs(v);
        }
        if (v<0) {
            con_total += abs(v);
            pos2con[i] = abs(v);
        }
        cities.push_back(make_tuple(i, v));        
        pos2procum[i] = pro_total;
        pos2concum[i] = con_total;
    } 
    if (pro_total<con_total) {
        cout<<"-1"<<endl;
        return 0;
    }

    //cout<<"n="<<n<<endl;
    //for (auto c: cities) cout<<"city: "<<get<0>(c)<<" "<<get<1>(c)<<" "<<pos2procum[get<0>(c)]<<" "<<pos2concum[get<0>(c)]<<endl;
        
    vector< tuple<int,int> > paths; // (len, startix)
    for (int i=0; i<cities.size()-1; ++i) {
        paths.push_back( make_tuple(get<0>(cities[i+1])-get<0>(cities[i]), i) );
    }
    sort(paths.begin(), paths.end(), greater< tuple<int,int> >());

    //for (auto p: paths) cout<<"path: len="<<get<0>(cities[get<0>(p)])<<" start="<<get<1>(p)<<endl;

    ullong total_length = 0;
    int firstpos=get<0>(cities.front()), lastpos=get<0>(cities.back());
    set<int> breaks = {firstpos, lastpos}, nbreaks = {-firstpos, -lastpos};
    for (auto& p: paths) {
        int ix=get<1>(p), len=get<0>(p), start=get<0>(cities[ix]), end=start+len;
        int le_start = -(*nbreaks.lower_bound(-start));
        int ge_end = *breaks.lower_bound(end);
        int left_con = pos2concum[start]-pos2concum[le_start]+pos2con[le_start];
        int left_pro = pos2procum[start]-pos2procum[le_start]+pos2pro[le_start];
        int right_con = pos2concum[ge_end]-pos2concum[end]+pos2con[end];
        int right_pro = pos2procum[ge_end]-pos2procum[end]+pos2pro[end];
        //cout<<"path: ix="<<ix<<" start="<<start<<" end="<<end<<" le_start="<<le_start<<" ge_end="<<ge_end;
        //cout<<" left_con="<<left_con<<" left_pro="<<left_pro<<" right_con="<<right_con<<" right_pro="<<right_pro<<endl;
        
        if (left_pro>=left_con && right_pro>=right_con) { //remove edge
            breaks.insert(start); breaks.insert(end);                       
            nbreaks.insert(-start); nbreaks.insert(-end);
            //cout<<" -> removed"<<endl;
        } else {
            total_length += len;
        }
    }

    cout<<total_length<<endl;
    return 0;
}