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

typedef long long ll;

int main() {
  int c;
  std::cin >> c;
  ll height = 0;
  ll current = 0;
  std::map<ll, int> bests;
  bests[0] = 0;
  for (int i = 0; i < c; i++) {
    std::cin >> current;
    height += current;
    if (height >= 0) {
      auto pos = bests.lower_bound(-height);
      int best = pos->second - 1;
      bests[-height] = pos->second - 1;

      pos = bests.lower_bound(-height);
      while (pos != bests.begin()) {
        auto prev = pos;
        prev--;
        if (prev->second > best) {
          bests.erase(prev);
        }
        else {
          break;
        }
      }
    }
  }
  if (height >= 0) {
    std::cout << c + bests[-height] << std::endl;
  }
  else {
    std::cout << -1 << std::endl;
  }

  return 0;
}