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
118
119
120
121
122
123
124
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;

#define PII          pair< int, int >
#define PLI          pair< long long, int >
#define VPII         vector< PII >
#define VPLI         vector< PLI >
#define MP           make_pair
#define REP(i,n)     for(int i=0;i<(n);++i)
#define FOR(i,a,b)   for (int i=(a); i<(b); ++i)
#define FORD(i,a,b)  for (int i=(a)-1; i>=(b); --i)
#define EACH(a, x)   for (auto& a : (x))
#define ALL(x)       (x).begin(), (x).end()

#define INF INT_MAX

int n;
vector<int> dp;
VPLI prefsums;
vector<long long> ps;

// https://codeforces.com/blog/entry/18051

void modify_dp(int p, int value) { 
    for (dp[p += n + 1] = value; p > 1; p >>= 1) {
        dp[p >> 1] = min(dp[p], dp[p ^ 1]);
    }
}

int query_dp(int l, int r) { 
    int res = INF;
    for (l += n + 1, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) {
            int v = dp[l++];
            if (v < res) {
                res = v;
            }
        }
        if (r & 1) {
            int v = dp[--r];
            if (v < res) {
                res = v;
            }
        }
    }
    return res;
}

int ub(long long v) {
    int begin = 0;
    int end = n + 1;
    while (end > begin) {
        int mid = (begin + end) / 2;
        long long vv = prefsums[mid].first;
        if (vv <= v) {
            begin = mid + 1;
        } else {
            end = mid;
        }
    }
    return begin;
    // REP(i, n + 1) {
    //     if (prefsums[i].first > v) {
    //         return i;
    //     }
    // }
    // return n;
}

int minv(int ptl) {
    return query_dp(0, ptl);
    // int m = INF;
    // REP(i, ptl) {
    //     if (dp[i] < m) {
    //         m = dp[i];
    //     } 
    // }
    // return m;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n;
    prefsums.reserve(n + 2);
    ps.reserve(n + 2);
    dp.reserve(2 * n + 4);
    prefsums.push_back(MP(0, 0));
    ps.push_back(0);
    long long x;
    REP(i, n) {
        cin >> x;
        prefsums.push_back(MP(prefsums.back().first + x, i + 1));
        ps.push_back(ps.back() + x);
    }
    for (int i = 0; i < 2 * n + 2; i++) {
        dp.push_back(INF);
    }

    sort(prefsums.begin(), prefsums.end());

    vector<int> mapping(n + 2, 0);
    int i = 0;
    EACH(elem, prefsums) {
        mapping[elem.second] = i;
        i++; 
    }

    modify_dp(mapping[0], n);
    REP(i, n) {
        int first_bad = ub(ps[i + 1]);
        int res = minv(first_bad);
        modify_dp(mapping[i + 1], res - 1);
    }

    int ans = dp[mapping[n] + n + 1];
    if(ans > n - 1) {
        ans = -1;
    }
    cout << ans << endl; 
}