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
#include <iostream>
#include <vector>
//#include <string>

#define INF 1e18

struct RangeTree {
    std::vector<long long> data;

    inline static int parent(int x) { return (x - 1) / 2; }
    inline static int left(int x) { return x * 2 + 1; }
    inline static int right(int x) { return x * 2 + 2; }
    inline int first_leaf() { return data.size() / 2; }

    RangeTree(int n) {
        int size = 1;
        while (size < n) size <<= 1;
        data.resize(size * 2 - 1);
    }

    void add(int from, int to, long long value) {
        int x = from + first_leaf();
        int y = to + first_leaf();
        data[x] += value;
        if (x != y) data[y] += value;
        while (parent(x) != parent(y)) {
            if (left(parent(x)) == x) data[right(parent(x))] += value;
            if (right(parent(y)) == y) data[left(parent(y))] += value;
            x = parent(x);
            y = parent(y);
        }
    }

    long long get(int i) {
        int node = i + first_leaf();
        long long ret = data[node];
        while (node > 0) {
            node = parent(node);
            ret += data[node];
        }
        return ret;
    }
};

int main(int argc, char** argv) {
    std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<long long> A(n);

    long long pos_sum = 0, neg_sum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> A[i];
        if (A[i] > 0) pos_sum += A[i];
        else neg_sum -= A[i];
    }

    if (pos_sum < neg_sum) {
        std::cout << -1;
        return 0;
    }

    //if (argc < 2 || std::string(argv[1]) != "brut") {
        RangeTree tree(n + 1);

        tree.add(0, 0, A[0]);
        for (int d = 1; d < n; ++d) {
            int idx = -1;
            int left = 0, right = d - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                long long val = tree.get(mid);
                if (val >= 0) {
                    idx = mid;
                    left = mid + 1;
                } else right = mid - 1;
            }

            tree.add(0, d - 1, A[d]);

            if (idx != -1) {
                tree.add(idx + 1, idx + 1, A[d] - tree.get(idx + 1));
            }
            if (idx != d - 1) {
                tree.add(d, d, -INF - tree.get(d));
            }

            //for (int k = d; k >= 0; --k) {
            //    if (tree.get(k) < -INF/2) std::cout << -INF << " "; else std::cout << tree.get(k) << " ";
            //}
            //std::cout << "\n";
        }
        for (int k = 0; k < n; ++k) {
            if (tree.get(n - k - 1) >= 0) {
                std::cout << k;
                return 0;
            }
        }
    //} else {
    //    std::vector<std::vector<long long>> D(n, std::vector<long long>(n));
    //    D[0][0] = A[0];
    //    for (int d = 1; d < n; ++d) {
    //        for (int k = 0; k <= d; ++k) {
    //            D[d][k] = -INF;
    //            if (k > 0) D[d][k] = std::max(D[d][k], D[d - 1][k - 1] + A[d]);
    //            if (k <= d - 1 && D[d - 1][k] >= 0) D[d][k] = std::max(D[d][k], A[d]);
    //            if (D[d][k] < -INF/2) std::cout << -INF << " "; else std::cout << D[d][k] << " ";
    //        }
    //        std::cout << "\n";
    //    }

    //    for (int k = 0; k < n; ++k) {
    //        if (D[n - 1][k] >= 0) {
    //            std::cout << k;
    //            return 0;
    //        }
    //    }
    //}


    return 0;
}