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

using namespace std;

#ifdef USE_CERR_LOG
#define LOG if (true) cerr
#else
#define LOG if (false) cerr
#endif

typedef long long ll;
typedef unsigned long long ull;

#ifdef USE_FILE_CIN
ifstream fin("../sis.in");
#define cin fin
#endif


const int Attack = 1;
const int Birth = 2;
const int Death = 3;

map<ll, int> sprats;
int spratCount;
int eventCount;


void readInitialData() {
    ll sprat;
    cin >> spratCount;
    
    for (int i=0; i<spratCount; i++) {
        cin >> sprat;
        sprats[sprat] ++;
    }
    
    cin >> eventCount;
}

void performAttack(ll initWeight, ll destWeight) {
    int eatenCount = 0;
    ll weight = initWeight;
    decltype(sprats) removedSprats;
    
    while (weight < destWeight) {
        if (sprats.empty()) {
            eatenCount = -1;
            break;            
        }
        
        auto it = sprats.lower_bound(weight);
        
        if (it == sprats.begin() && it->first >= weight) {
            eatenCount = -1;
            break;            
        }
        
        if (it == sprats.end() || it->first >= weight) {
            it --;
        }
        
        weight += it->first;
        eatenCount ++;        
        removedSprats[it->first] ++;
        
        if (--it->second == 0) {
            sprats.erase(it);
        }
    }
    
    for (auto& sprat : removedSprats) {
        sprats[sprat.first] += sprat.second;
    }
    
    cout << eatenCount << endl;
}

inline void addSprat(ll sprat) {
    sprats[sprat] ++;
}

inline void removeSprat(map<ll, int>& sprats, ll sprat) {
    auto it = sprats.find(sprat);
    
    if (--it->second == 0) {
        sprats.erase(it);
    }
}

void processEvents() {
    int eventType;
    ll weight1, weight2;
    
    for (int i=0; i<eventCount; i++) {
        cin >> eventType >> weight1;
        switch (eventType) {
            case Attack:
                cin >> weight2;
                performAttack(weight1, weight2);
                break;
            case Birth:
                addSprat(weight1);
                break;
            case Death:
                removeSprat(sprats, weight1);
                break;                
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    
    readInitialData();
    processEvents();
    
    return 0;
}