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
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll INFLL = LLONG_MAX / 2;

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  int timer = 0;
  vector <ll> weights = {0};
  unordered_map<ll, vector <int>> times;
  vector<pair<ll, int>> events;
  auto append = [&](ll x) {
    timer++;
    weights.push_back(x);
    times[x].push_back(timer);
    events.emplace_back(x, timer);
  };
  for (int i=0; i<n; i++) {
    ll w;
    cin >> w;
    append(w);
  }
  int q;
  cin >> q;
  int pot2 = 1<<(32-__builtin_clz(n+q));
  vector <pair <ll, int>> tree(pot2);
  vector <pair<ll, ll>> queries;
  vector <int> types(q);
  for (int i=0; i<q; i++) {
    cin >> types[i];
    if (types[i] == 1) {
      ll st, ko;
      cin >> st >> ko;
      queries.emplace_back(st, ko);
    } else if (types[i] == 2) {
      ll w;
      cin >> w;
      append(w);
      queries.emplace_back(timer, -2);
    } else {
      ll w;
      cin >> w;
      queries.emplace_back(times[w].back(), -3);
      times[w].pop_back();
    }
  }
  vector <int> who(timer+3);
  vector <ll> value(timer+3);
  sort(events.begin(), events.end());
  for (int i=1; i<=timer; i++) {
    value[i] = events[i-1].first;
    who[events[i-1].second] = i;
  }
  set <pair <ll, int>> active;
  active.emplace(INFLL, timer+1);
  value[timer+1] = INFLL;
  auto change_tree = [&](int ix, ll val, int m) {
    for (int i=ix; i<(int)tree.size(); i+=(i&(-i))) {
      tree[i].first += val * m;
      tree[i].second += m;
    }
  };
  auto turn_on = [&](int tim) {
    // cerr << "TURN_ON " << tim << " " << value[tim] << "\n";
    active.emplace(value[tim], tim);
    change_tree(tim, value[tim], +1);
  };
  auto turn_off = [&](int tim) {
    // cerr << "TURN_OFF " << tim << " " << value[tim] << "\n";
    active.erase({value[tim], tim});
    change_tree(tim, value[tim], -1);
  };
  auto query = [&](pair<ll, ll> q) {
    ll st, ko;
    tie(st, ko) = q;
    int ret = 0;
    vector <pair <int, int> > steps = {{0, 0}};
    while (st < ko) {
      if ((int)steps.size() >= 2) {
        auto& second_pre = steps[steps.size()-2], pre = steps[steps.size()-1];
        if (pre.first-1==second_pre.second) {
          second_pre.second = pre.second;
          steps.pop_back();
          continue;
        }
      }
      auto cur = (*active.lower_bound({st, 0}));
      if (steps.back() == make_pair(0, cur.second-1)) return -1;
      if (steps.back().second < cur.second-1) {
        steps.emplace_back(cur.second, cur.second-1);
      }
      int right =  steps[steps.size()-1].first - 1;
      ll needed =  min(ko, value[cur.second]+1)-st;
      // cerr << "NEEDED" << needed << "\n";
      ll found = 0;
      for (int i=right; i>0; i-=(i&(-i))) {
        found += tree[i].first;
        st += tree[i].first;
        ret += tree[i].second;
      }
      if (found < needed) return -1;
      int pos = 0;
      for (int ch=pot2/2; ch>0; ch/=2) {
        if (pos+ch > right) continue;
        if (tree[pos+ch].first+needed <= found) {
          pos += ch;
          needed += tree[pos].first;
        }
      }
      int left = max(pos, steps[steps.size()-2].second);
      steps.back().first = left+1;
      for (int i=left; i>0; i-=(i&(-i))) {
        st -= tree[i].first;
        ret -= tree[i].second;
      }
    }
    return ret;
  };
  for (int i=1; i<=n; i++) turn_on(who[i]);
  for (int i=0; i<q; i++) {
    if (types[i] == 1) cout << query(queries[i]) << "\n";
    else if (types[i] == 2) turn_on(who[queries[i].first]);
    else turn_off(who[queries[i].first]);
  }
}