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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
// Author: Kamil Nizinski
// NOLINT(legal/copyright)
#ifdef LOCAL
#ifdef COLOR
#include "bits/cp_local_color.h"
#else
#include "bits/cp_local.h"
#endif
#else
#include "bits/stdc++.h"
#define debug_arr(arr_name, first, last)
#define debug(...)
#define cerr if (false) cerr
#define speed_of_cin_and_cout ios_base::sync_with_stdio(0), cin.tie(0)
#define local if (false)
#endif
#define ft first
#define sd second
#define sz(a) (static_cast<int>((a).size()))
using namespace std;  // NOLINT(build/namespaces)
typedef int64_t LL;
typedef uint64_t LLU;
typedef long double LD;
typedef pair<int, int> PII;
const int kMaxQ = 100007;
struct Node {
  int number;
  LL weight;
  LL max_weight;
  Node *left;
  Node *right;
  bool all_eaten;
  bool has_changed;
  Node(int ini_number = 0, LL ini_weight = LL{0}, LL ini_max_weight = LL{-1},
    Node *ini_left = nullptr, Node *ini_right = nullptr,
    bool ini_all_eaten = false, bool ini_has_changed = false) {
    number = ini_number;
    weight = ini_weight;
    max_weight = ini_max_weight;
    left = ini_left;
    right = ini_right;
    all_eaten = ini_all_eaten;
    has_changed = ini_has_changed;
  }
};
typedef Node* Tree;
Tree build_tree(int low, int high, const vector<pair<LL, int>> &sprats) {
  if (low + 1 == high) {
    if (sprats[low].sd != -1) {
      cerr << "Zero\n";
      return new Node();
    }
    else {
      debug(1, sprats[low].ft, sprats[low].ft);
      return new Node(1, sprats[low].ft, sprats[low].ft);
    }
  }
  int mid = (low + high) >> 1;
  Tree l = build_tree(low, mid, sprats);
  Tree r = build_tree(mid, high, sprats);
  return new Node(l->number + r->number, l->weight + r->weight,
    max(l->max_weight, r->max_weight), l, r);
}
void update_values_of_nonleaf(Tree t) {
  Tree l = t->left;
  Tree r = t->right;
  t->number = l->number + r->number;
  t->weight = l->weight + r->weight;
  t->max_weight = max(l->max_weight, r->max_weight);
}
pair<int, LL> eat_at_least_from_right_in(Tree t, int low, int high, LL lower_need, int r) {
  // lower_need > LL{0} or actually:
  debug(low, high);
  debug(lower_need);
  if (lower_need <= LL{0}) return {0, LL{0}};
  if (t->weight == LL{0}) return {0, LL{0}};
  if (low >= r) return {0, LL{0}};
  if (high <= r) {
    if (t->weight <= lower_need || (low + 1 == high)) {
      pair<int, LL> result = {t->number, t->weight};
      t->number = 0;
      t->weight = LL{0};
      t->max_weight = LL{-1};
      t->has_changed = true;
      debug(result);
      return result;
    }
  }
  int mid = (low + high) >> 1;
  pair<int, LL> result_r = eat_at_least_from_right_in(t->right, mid, high, lower_need, r);
  lower_need -= result_r.sd;
  if (result_r.sd > LL{0}) t->has_changed = true;
  pair<int, LL> result_l = eat_at_least_from_right_in(t->left, low, mid, lower_need, r);
  if (result_l.sd > LL{0}) t->has_changed = true;
  update_values_of_nonleaf(t);
  pair<int, LL> result = {result_l.ft + result_r.ft, result_l.sd + result_r.sd};
  debug(result);
  return result;
}
void tidy_up(Tree t, int low, int high, const vector<pair<LL, int>> &sprats) {
  if (t->has_changed) {
    if (low + 1 == high) {
      // (*t) = Node(1, sprats[low].ft, sprats[low].ft);
      t->number = 1;
      t->weight = sprats[low].ft;
      t->max_weight = sprats[low].ft;
    } else {
      int mid = (low + high) >> 1;
      tidy_up(t->left, low, mid, sprats);
      tidy_up(t->right, mid, high, sprats);
      update_values_of_nonleaf(t);
    }
    t->has_changed = false;
  }
}
int find_first_with_geq_weight(Tree t, int low, int high, LL weight) {
  // It exists.
  if (low + 1 == high) return low;
  int mid = (low + high) >> 1;
  if (t->left->max_weight >= weight)
    return find_first_with_geq_weight(t->left, low, mid, weight);
  else
    return find_first_with_geq_weight(t->right, mid, high, weight);
}

void switch_presence(Tree t, int low, int high, int idx, const vector<pair<LL, int>> &sprats) {
  if (low + 1 == high) {
    if (t->number == 1) {
      // (*t) = Node();
      t->number = 0;
      t->weight = LL{0};
      t->max_weight = LL{-1};
    } else {
      // (*t) = Node(1, sprats[low].ft, sprats[low].ft);
      t->number = 1;
      t->weight = sprats[low].ft;
      t->max_weight = sprats[low].ft;
    }
  } else {
    int mid = (low + high) >> 1;
    if (idx < mid)
      switch_presence(t->left, low, mid, idx, sprats);
    else
      switch_presence(t->right, mid, high, idx, sprats);
    update_values_of_nonleaf(t);
  }
}
void solve() {
  int original_n;
  cin >> original_n;
  static vector<pair<LL, int>> sprats_sorted_by_weight;  // weight, event index
  for (int i = 0; i < original_n; i++) {
    LL w;
    cin >> w;
    sprats_sorted_by_weight.emplace_back(w, -1);
  }
  int q;
  cin >> q;
  static array<pair<int, pair<LL, int>>, kMaxQ> events;
  // type, 1 -> {s, (k - LL{1})'s index}, 2-> {LL{0}, w's index}, 3 -> {w, 0}
  for (int i = 0; i < q; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      LL s, k;
      cin >> s >> k;
      events[i] = {type, {s, 0}};
      sprats_sorted_by_weight.emplace_back(k - LL{1}, i);
    } else {
      LL w;
      cin >> w;
      if (type == 2) {
        sprats_sorted_by_weight.emplace_back(w, i);
        events[i].ft = 2;
      }
      else
        events[i] = {type, {w, 0}};
    }
  }
  sort(sprats_sorted_by_weight.begin(), sprats_sorted_by_weight.end());
  debug(sprats_sorted_by_weight);
  int n = sz(sprats_sorted_by_weight);
  debug(n);
  for (int i = 0; i < n; i++) {
    int event_idx = sprats_sorted_by_weight[i].sd;
    if (event_idx != -1) {
      if (events[event_idx].ft == 1)
        events[event_idx].sd.sd = i;
      else
        events[event_idx].sd = {LL{0}, i};
    }
  }
  Tree tree = build_tree(0, n, sprats_sorted_by_weight);
  cerr << "Now events:\n";
  for (int i = 0; i < q; i++) {
    auto event = events[i];
    int type = event.ft;
    debug(i, event);
    if (type == 1) {
      LL pike_weight = event.sd.ft;
      int wanted_sprat = event.sd.sd;
      switch_presence(tree, 0, n, wanted_sprat, sprats_sorted_by_weight);
      int answer = 0;
      while (pike_weight <= sprats_sorted_by_weight[wanted_sprat].ft) {
        debug(pike_weight);
        int goal_idx = find_first_with_geq_weight(tree, 0, n, pike_weight);
        debug(goal_idx);
        LL goal_weight = sprats_sorted_by_weight[goal_idx].ft;
        debug(goal_weight);
        // I need to exceed the goal weight.
        pair<int, LL> result = eat_at_least_from_right_in(tree, 0, n, LL{1} + goal_weight - pike_weight, goal_idx);
        debug(result);
        if (pike_weight + result.sd <= goal_weight) {
          answer = -1;
          break;
        }
        answer += result.ft;
        pike_weight += result.sd;
      }
      cout << answer << "\n";
      debug(answer);
      tidy_up(tree, 0, n, sprats_sorted_by_weight);
      cerr << "Tidied_up\n";
      switch_presence(tree, 0, n, wanted_sprat, sprats_sorted_by_weight);
    } else {
      if (type == 2) {
        debug(event.sd.sd);
        switch_presence(tree, 0, n, event.sd.sd, sprats_sorted_by_weight);
      } else {
        int idx = find_first_with_geq_weight(tree, 0, n, event.sd.ft);
        switch_presence(tree, 0, n, idx, sprats_sorted_by_weight);
      }
    }
  }
}

int main() {
  speed_of_cin_and_cout;
  int test_cases_num = 1;
//   cin >> test_cases_num;
  for (int i = 1; i <= test_cases_num; i++) {
    local if (test_cases_num > 1) cerr << "Test #" << i << ":\n";
    solve();
    local if (test_cases_num > 1) cerr << "End of test #" << i << ".\n";
  }
  return 0;
}