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

const int max_n = 500010;
const int czapa = 524288;
const int inf = 1000000000;

int n;
int input[max_n];
long long prefix_sum[max_n];
std::pair<long long, int> sorted_prefixes[max_n];
int reverse_mapping[max_n];

struct TreeNode {
    int diff;
    int min;
};

TreeNode tree[2*czapa + 1];

int find_min(int index, int limit, int range_left, int range_right) {
    if (range_left == range_right) {
        tree[index].min += tree[index].diff;
        tree[index].diff = 0;
        return tree[index].min;
    } else {
        tree[2*index].diff += tree[index].diff;
        tree[2*index + 1].diff += tree[index].diff;
        tree[index].min += tree[index].diff;
        tree[index].diff = 0;

        int middle = (range_left + range_right) / 2;

        if (limit > middle) {
            int ret = tree[2*index].min + tree[2*index].diff;
            return std::min(ret, find_min(2*index + 1, limit, middle + 1, range_right));
        } else {
            return find_min(2*index, limit, range_left, middle);
        }
    }
}

void add_one() {
    tree[1].diff += 1;
}

void set_val(int index, int elem, int val, int range_left, int range_right) {
    if (range_left == range_right) {
        tree[index].min = val;
        tree[index].diff = 0;
    } else {
        tree[2*index].diff += tree[index].diff;
        tree[2*index + 1].diff += tree[index].diff;
        tree[index].diff = 0;

        int middle = (range_left + range_right) / 2;

        if (elem > middle) {
            set_val(2*index + 1, elem, val, middle + 1, range_right);
        } else {
            set_val(2*index, elem, val, range_left, middle);
        }
        tree[index].min = std::min(tree[2*index].min + tree[2*index].diff, tree[2*index + 1].min + tree[2*index + 1].diff);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &input[i]);
    input[n++] = 0;
    prefix_sum[0] = 0;
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + input[i];
        sorted_prefixes[i].first = prefix_sum[i];
        sorted_prefixes[i].second = i;
//        printf ("prefix_sum[%d] = %d\n", i, prefix_sum[i]);
    }
    std::sort(sorted_prefixes, sorted_prefixes + n);
    for (int i = 0; i < n; ++i) {
        reverse_mapping[sorted_prefixes[i].second] = i;
//        printf ("reverse_mapping[%d] = %d\n", i, sorted_prefixes[i].second);
    }

    for (int i = 0; i < 2 * czapa + 1; i++) {
        tree[i].diff = 0;
        tree[i].min = inf;
    }

    set_val(1, reverse_mapping[0], 0, 0, n - 1);
    int mm;
    for (int i = 1; i < n; ++i) {
        int range = reverse_mapping[i];
        mm = find_min(1, range, 0, n - 1);
        add_one();
        if (mm < inf) {
            set_val(1, range, mm, 0, n - 1);
        }
    }
    printf("%d\n", mm < inf ? mm : -1);
    return 0;
}