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
#include<bits/stdc++.h>
using namespace std;

  const int NN=500010;
  long long AA[NN]={};
  long long BB[NN]={};
  long long PP[NN]={};
  int pocz,kon,dl,qq,typo,ss,kk;

int BinSerch(long long w){
  int a=pocz, b=kon;
  if (w>AA[b]) return b;
  if (w<=AA[a]) return -1;
  while(a<b-1){
    int sr=(a+b)/2;
    if(AA[sr]<w) a=sr;
    else b=sr;
  }
  return a;
}

void dodaj(long long w){
  int sr=(pocz+kon)/2;
  if(w<AA[sr]){
    pocz--;
    int t=pocz;
    while(w>AA[t+1]) { AA[t]=AA[t+1]; BB[t]=BB[t+1]; t++; }
    AA[t]=w;
    for(int e=t;e<=kon;e++) BB[e] += w;
  }
  else{
    kon++;
    int t=kon;
    while(w<AA[t-1]) { AA[t]=AA[t-1]; BB[t]=BB[t-1]+w; t--; }
    AA[t]=w;
    BB[t] = BB[t-1]+w;
  }
  return;
}

void usun(long long w){
  int gdzie = BinSerch(w); // szuka MNIEJSZEJ !!!!!!
  if (gdzie == -1) { pocz++; for(int i=pocz;i<=kon;i++) BB[i] -= w; return; }
  gdzie++;
  int sr=(pocz+kon)/2;
  if(gdzie<sr){
    pocz++;
    for(int i=pocz;i<=gdzie;i++) {AA[i]=AA[i-1]; BB[i]=BB[i-1];}
    for(int i=gdzie+1;i<=kon;i++) BB[i] -= w;
  }
  else{
    for(int i=gdzie;i<kon;i++) {AA[i]=AA[i+1]; BB[i] = BB[i+1]-w;}
    kon--;
  }
  return;
}

int main()
{
  cin >> dl;
  pocz=NN/2-dl/2;
  kon=pocz+dl-1;
  for(int i=pocz;i<=kon;i++) cin >> AA[i];
  sort(AA+pocz,AA+kon+1);
  BB[pocz]=AA[pocz];
  for(int i=pocz+1;i<=kon;i++) BB[i]=BB[i-1]+AA[i];

  cin >> qq;
  for(int i=0;i<qq;i++){
    cin >> typo;
    if(typo==1){
        cin >> ss >> kk;
        int licz=0;
        if(ss<kk){
           for(int t=pocz;t<=kon;t++) PP[t]=1;
           while(ss<kk){
             int gdzie = BinSerch(ss);
             if(gdzie == -1) {licz =-1; kk=0; }
             else{
               while(PP[gdzie]==0 && gdzie>= pocz) gdzie--;
               if(gdzie>=pocz){
                 ss += AA[gdzie];
                 PP[gdzie]=0;
                 licz++;
               }
               else {licz =-1; kk=0; }
             }
           }
        }
        cout << licz << endl;
    }
    else if(typo==2){
      cin >> ss;
      dodaj(ss);
    }
    else{
      cin >> ss;
      usun(ss);
    }
  }

  return 0;
}