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

using namespace std;

#define f first
#define s second

const int MAXN = 3e5 + 3;

map<long long, long long> ile;
map<long long, long long> akt;
set<long long> q;

int main() {
    int n, z, cs;
    long long w, x, y, ter;
    long long wyn, nas, wz;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &w);
        ile[w]++;
    }
    q.insert(-1);
    for (auto it:ile)
        q.insert(it.f);
    auto it = q.begin(), iter = q.begin();
    bool por;
    scanf("%d", &z);
    while (z--) {
        scanf("%d", &cs);
        if (cs == 1) {
            scanf("%lld %lld", &x, &y);
            wyn = 0;
            por = false;
            akt.clear();
            while (x < y) {
                iter = q.lower_bound(x);
                if (iter == q.end() || *iter >= x)
                    iter--;
                it = iter;
                iter++;
                ter = *it;
                if (iter == q.end() || *iter > y)
                    nas = y - 1;
                else
                    nas = *iter;
                if (*it == -1) {
                    por = true;
                    break;
                }
                if (x + ter * ile[ter] <= nas) {
                    x += ter * ile[ter];
                    q.erase(ter);
                    akt[ter] = ile[ter];
                    wyn += ile[ter];
                    ile[ter] = 0;
                }
                else {
                    wz = (nas - x) / ter + 1;
                    if (akt[ter] == 0)
                        akt[ter] = ile[ter];
                    ile[ter] -= wz;
                    x += wz * ter;
                    wyn += wz;
                    if (ile[ter] == 0)
                        q.erase(ter);
                }
            }
            for (auto it2:akt) {
                if (ile[it2.f] == 0)
                    q.insert(it2.f);
                ile[it2.f] = it2.s;
            }
            if (por)
                printf("-1\n");
            else
                printf("%lld\n", wyn);
        }
        else if (cs == 2) {
            scanf("%lld", &x);
            ile[x]++;
            if (ile[x] == 1)
                q.insert(x);
        }
        else {
            scanf("%lld", &x);
            ile[x]--;
            if (ile[x] == 0)
                q.erase(x);
        }
    }
    return 0;
}