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

int n;
std::vector<long long> values;
std::vector<long> dists;
long result = -1L;

std::vector<std::pair<long long, long>> positive_states[2]; // (current surplus, current length)
std::vector<std::pair<long long, long>> negative_states[2]; // (current surplus, current length)

void read() {
  scanf("%d\n", &n);
  int lasti = 0;
  for (int i=0; i<n; i++) {
    long x;
    scanf("%ld", &x);
    if (x != 0) {
      values.emplace_back((long long) x);
      dists.emplace_back((long) (i - lasti));
      lasti = i;
    }
  }
}

int main() {
  read();
  int index_curr = 0;
  int index_next = 1;
  positive_states[index_curr].emplace_back(0, 0);
  for(int i=0; i<values.size(); i++) {
    positive_states[index_next].clear();
    negative_states[index_next].clear();
    long value = values[i];
    long dist = dists[i];
    long shortest_positive = -1L;
    for (auto state: positive_states[index_curr]) {
      if (shortest_positive < 0 || state.second < shortest_positive) {
        shortest_positive = state.second;
      }
    }
    if (shortest_positive >= 0) {
      bool should_be_added = true;
      for (auto state: positive_states[index_curr]) {
        long long surplus = state.first + value;
        long length = state.second + dist;
        if (length < shortest_positive || surplus > value) { // is it worth considering
          if (length <= shortest_positive && surplus >= value) {
            should_be_added = false;
          }
          if (surplus >= 0) {
            positive_states[index_next].emplace_back(surplus, length);
          } else {
            negative_states[index_next].emplace_back(surplus, length);
          }
        }
      }
      for (auto state: negative_states[index_curr]) {
        long long surplus = state.first + value;
        long length = state.second + dist;
        if (length < shortest_positive || surplus > value) {
          if (length <= shortest_positive && surplus >= value) {
            should_be_added = false;
          }
          if (surplus >= 0) {
            positive_states[index_next].emplace_back(surplus, length);
          } else {
            negative_states[index_next].emplace_back(surplus, length);
          }
        }
      }
      if (should_be_added) {
        if (value > 0) {
          positive_states[index_next].emplace_back(value, shortest_positive);
        } else {
          negative_states[index_next].emplace_back(value, shortest_positive);
        }
      }
    } else {
      for (auto state: positive_states[index_curr]) {
        long long surplus = state.first + value;
        long length = state.second + dist;
        if (surplus >= 0) {
          positive_states[index_next].emplace_back(surplus, length);
        } else {
          negative_states[index_next].emplace_back(surplus, length);
        }
      }
      for (auto state: negative_states[index_curr]) {
        long long surplus = state.first + value;
        long length = state.second + dist;
        if (surplus >= 0) {
          positive_states[index_next].emplace_back(surplus, length);
        } else {
          negative_states[index_next].emplace_back(surplus, length);
        }
      }
    }
    index_curr = ((index_curr + 1) & 1);
    index_next = ((index_next + 1) & 1);
  }

  for (auto state : positive_states[index_curr]) {
    if (result < 0 || state.second < result) {
      result = state.second;
    }
  }
  printf("%ld\n", result);
  return 0;
}