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
#include <cstdio>
#include <string>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> edge; // first - cost, second - first point

typedef long long ll;

const int SIZE = 500005;

ll sum_left[SIZE], sum_right[SIZE];
vector<edge> edges;
vector<int> points;
int n, k;

struct Range {
  int end;
  ll sub_left, sub_right;
};

map<int, Range> divs;


int main() {
  scanf("%d", &n);
  int v;
  int last_pos = -1;
  int total_cost = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &v);
    if (v != 0) {
      points.push_back(v);
      if (points.size() > 1) {
        edges.push_back(edge(i - last_pos, points.size() - 2));
        total_cost += edges.back().first;
      }
      last_pos = i;
    }
  }
  if (points.size() == 0) {
    printf("0\n");
    return 0;
  }
  sort(edges.rbegin(), edges.rend());
  sum_left[0] = points[0];
  sum_right[points.size() - 1] = points.back();
  for (int i = 1; i < points.size(); ++i) {
    sum_left[i] = sum_left[i-1] + points[i];
    sum_right[points.size() - 1 - i] = sum_right[points.size() - i] + points[points.size() - 1 - i];
  }
  if (sum_right[0] < 0) {
    printf("-1\n");
    return 0;
  }
  // for (int i = 0; i < points.size(); ++i) {
  //   printf("Point %d: %d [sum_left: %lld sum_right: %lld]\n", i, points[i], sum_left[i], sum_right[i]);
  // }
  // for (int i = 0; i < edges.size(); ++i) {
  //   printf("Edge: [%d, %d] - %d\n", edges[i].second, edges[i].second + 1, edges[i].first);
  // }
  {
    Range r;
    r.end = points.size() - 1;
    r.sub_left = 0;
    r.sub_right = 0;
    divs[0] = r;
  }
  for (int i = 0; i < edges.size(); ++i) {
    int edge_from = edges[i].second;
    int edge_to = edge_from + 1;
    int cost = edges[i].first;
    // printf("Processing edge: [%d, %d]: %d\n", edge_from, edge_to, cost);
    map<int, Range>::iterator it = divs.upper_bound(edge_from);
    --it;
    Range &r = it->second;
    // printf("Found range [%d, %d], (sub_left = %lld, sub_right = %lld)\n", it->first, r.end, r.sub_left, r.sub_right);
    if (sum_right[edge_to] - r.sub_right >= 0 && sum_left[edge_from] - r.sub_left >= 0) {
      // printf("Range is splitable\n");
      total_cost -= cost;
      Range right_range;
      right_range.end = r.end;
      right_range.sub_left = sum_left[edge_from];
      right_range.sub_right = r.sub_right;
      divs[edge_to] = right_range;
      r.end = edge_from;
      r.sub_right = sum_right[edge_to];
    }
  }
  printf("%d\n", total_cost);
  return 0;
}