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
// Karol Kosinski 2020
#include <cstdio>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;

typedef long long LL;
constexpr int NX = 5'00'003;
constexpr LL INFTY = 1'000'000'000'000'000'001LL;

constexpr int R2K(int x)
{
    int r = 1;
    while (r < x) r <<= 1;
    return r;
}

struct Node { LL mx; };

LL to_add;
int n2;
Node T[R2K(NX) << 1];

inline int parent(int x) { return x >> 1; }
inline int left(int x) { return x << 1; }
inline int right(int x) { return (x << 1) | 1; }

inline void update_all(int v) { to_add += v; };

void insert(int k, LL v)
{
    v -= to_add;
    int j = n2 + k;
    while (j > 0)
    {
        if (T[j].mx >= v) return;
        T[j].mx = v;
        j = parent(j);
    }
}

int find_max_key()
{
    if (T[1].mx == -INFTY)
    {
        DEBUG("empty\n");
        return 0;
    }
    DEBUG("to_add: %lld\n", to_add);
    int j = 1;
    while (j < n2)
    {
        if (T[right(j)].mx + to_add >= 0)
            j = right(j);
        else
            j = left(j);
    }
    DEBUG("[%d] %lld\n", j - n2, T[j].mx + to_add);
    return (T[j].mx + to_add >= 0) ? j - n2 : -1;
}

void init_tree(int n)
{
    n2 = R2K(n);
    FOR(i,0,n2)
    {
        T[left(i)].mx = -INFTY;
        T[right(i)].mx = -INFTY;
    }
}

int main()
{
    int n, a, counter = 0;
    scanf("%d", &n);
    init_tree(n);
    FOR(i,0,n)
    {
        scanf("%d", &a);
        if (a == 0)
        {
            ++ counter;
            continue;
        }
        int k = find_max_key();
        update_all(a);
        DEBUG("(%d / %d)\n", counter, a);
        if (k != -1)
        {
            DEBUG("* (%d / %d)\n", k + counter, a);
            insert(k + counter, a);
        }
        counter = 1;
    }
    int res = find_max_key();
    printf("%d\n", (res == -1) ? -1 : n - counter - res);
    return 0;
}