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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  int n, q, q_type;
  long long int w, s, k;
  cin >> n;
  std::multiset<long long int> fish;

  for (int i = 0; i < n; i++) {
    cin >> w;
    fish.insert(w);
  }

  cin >> q;

  for (int i = 0; i < q; i++) {
    cin >> q_type;
    if (q_type == 1) {
      cin >> s >> k;
      std::vector<long long int> removed_fish;

      if (s >= k) {
        cout << 0 << endl;
        continue;
      }

      if (fish.size() == 0) {
        cout << -1 << endl;
        continue;
      }

      int count_fish = 0;

      while (true) {
        auto k_it = fish.upper_bound(s - 1);
        if (k_it == fish.begin()) {
          cout << -1 << endl;
          break;
        }

        if (k_it == fish.end()) {
          k_it--;
        }

        if (*k_it >= s) {
          k_it--;
        }
        s += *k_it;
        count_fish++;
        removed_fish.push_back(*k_it);
        fish.erase(k_it);

        if (s >= k) {
          cout << count_fish << endl;
          break;
        }

        if (fish.size() == 0) {
          cout << -1 << endl;
          break;
        }
      }

      for (int j = 0; j < removed_fish.size(); j++) {
        fish.insert(removed_fish[j]);
      }
    } else if (q_type == 2) {
      cin >> w;
      fish.insert(w);
    } else if (q_type == 3) {
      cin >> w;
      auto it = fish.find(w);
      fish.erase(it);
    }
  }

  return 0;
}