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
115
116
117
/// Radoslaw Mysliwiec 2020
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
#define F first
#define S second
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define endl '\n'
#define dd cout << " debug";
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using pi = pair<int,int>;
using pll = pair<ll,ll>;
using matrix = vector<vll>;
using ordered_set = tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update>;
 
const int N = 500100;  // limit for array size
int n, m;  // array size
int t[2 * N];
int h ;
int d[N];  
vector<int> tab(500100, 0);
vector<pll> pref;

void apply(int p, int value) {
  t[p] += value;
  if (p < n) d[p] += value;
}

void build(int p) {
  while (p > 1) p >>= 1, t[p] = min(t[p<<1], t[p<<1|1]) + d[p];
}

void push(int p) {
  for (int s = h; s > 0; --s) {
    int i = p >> s;
    if (d[i] != 0) {
      apply(i<<1, d[i]);
      apply(i<<1|1, d[i]);
      d[i] = 0;
    }
  }
}

void inc(int l, int r, int value) {
  l += n, r += n;
  int l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1) apply(l++, value);
    if (r&1) apply(--r, value);
  }
  build(l0);
  build(r0 - 1);
}

int query(int l, int r) {
  l += n, r += n;
  push(l);
  push(r - 1);
  int res = 2e9;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = min(res, t[l++]);
    if (r&1) res = min(t[--r], res);
  }
  return res;
}

void wypisz(){
    for (int i=0; i<=19; ++i)
        cout << query(i, i+1) << ' ';
    cout << endl;
}

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

    cin >> m;
    n = m + 2;
    h = sizeof(int) * 8 - __builtin_clz(n);
    pref.resize(m+1);
    pref[0] = {0, 0};
    for (int i=1; i<=m; ++i) {
        cin >> tab[i];
        pref[i].F = tab[i] + pref[i-1].F;
        pref[i].S = i;
    }
    sort(ALL(pref));

    ll _pref = 0;
    int res;
    inc(0, n, 1e9);

    for (int i=0; i<=m; ++i) {
        _pref += ll(tab[i]);
        int ile_niewiekszych = upper_bound(pref.begin(), pref.end(), make_pair(_pref, ll(i-1))) - pref.begin();
        //cout << ile_niewiekszych << "     ";
        int best = query(0, ile_niewiekszych);
        if (i == 0) best = 0;
        inc(ile_niewiekszych, ile_niewiekszych+1, best - 1 - query(ile_niewiekszych, ile_niewiekszych+1));
        inc(0, n, 1);
        if (i == m) {
            int xd = query(ile_niewiekszych, ile_niewiekszych+1);
            if (xd > 1e6) cout << -1 << endl;
            else cout << xd << endl;
            return 0;
        }
    }
}