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
#include <bits/stdc++.h>

using namespace std;

const int N = 500000 + 50;
const int INF = 2000000000 + 50;

int t[N];
int a[N];
int dp[N];
long long pref[N];
int order[N], pos[N];
int n;

bool comp(int x, int y) {
  return pref[x] < pref[y];
}

inline void Update(int pos, int val) {
  for (int i = pos; i < N; i += i&-i) {
    t[i] = min(t[i], val);
  }
}
inline int PrefMin(int r) {
  int ans = INF;
  while(r > 0) {
    ans = min(ans, t[r]);
    r -= r&-r;
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pref[i] = a[i] + pref[i - 1];
    order[i] = i;
  }
  sort(order, order + n + 1, comp);

  int prev_pos = 0;
  for (int i = 0; i <= n; i++) {
    if (i != 0 && pref[order[i]] == pref[order[i - 1]]) {
      pos[order[i]] = prev_pos;
    }
    else {
      pos[order[i]] = ++prev_pos;
    }
  }
  fill(t, t + N, INF);
  Update(pos[0], 0);

  for (int i = 1; i <= n; i++) {
    if (a[i] >= 0) {
      dp[i] = dp[i - 1];
    }
    else {
      dp[i] = INF;
    }
    dp[i] = min(dp[i], i - 1 + PrefMin(pos[i]));
    Update(pos[i], -i + dp[i]);
  }

  if (dp[n] >= INF) {
    dp[n] = -1;
  }
  cout << dp[n];

  return 0;
}