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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=400010,M=1111111;
const ll inf=1LL<<60;
int n,m,q,i,ce,have[N];
ll a[N],e[N],op[N][3];
int POS,tag[M];ll cnt[M],sum[M];
int C;ll NXT,SUM,CNT;
int pool[N][3],cp;
void build(int x,int a,int b){
  if(a==b){
    cnt[x]=have[a];
    sum[x]=cnt[x]*e[a];
    return;
  }
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
  cnt[x]=cnt[x<<1]+cnt[x<<1|1];
  sum[x]=sum[x<<1]+sum[x<<1|1];
}
void change(int x,int a,int b,int c,ll A,ll B){
  sum[x]+=A;
  cnt[x]+=B;
  if(a==b)return;
  int mid=(a+b)>>1;
  if(c<=mid)change(x<<1,a,mid,c,A,B);else change(x<<1|1,mid+1,b,c,A,B);
}
//tag=pos means zero
void getnxt(int x,int a,int b){
  if(NXT)return;
  if(tag[x]==POS)return;
  if(!cnt[x])return;
  if(a==b){
    NXT=e[a];
    return;
  }
  int mid=(a+b)>>1;
  if(C<=mid)getnxt(x<<1,a,mid);
  getnxt(x<<1|1,mid+1,b);
}
void eat(int x,int a,int b){
  if(SUM>NXT)return;
  if(tag[x]==POS)return;
  if(!cnt[x])return;
  if(b<=C){
    if(SUM+sum[x]<=NXT){
      SUM+=sum[x];
      CNT+=cnt[x];
      tag[x]=POS;
      return;
    }
    if(a==b){
      //o>(NXT-SUM/e[a])
      ll tmp=(NXT-SUM)/e[a];
      while(tmp*e[a]+SUM<=NXT)tmp++;
      //if(tmp>cnt[x]||tmp<1)while(1);
      pool[++cp][0]=a;
      pool[cp][1]=tmp;
      ll val=tmp*e[a];
      for(;x;x>>=1)cnt[x]-=tmp,sum[x]-=val;
      SUM+=val;
      CNT+=tmp;
      return;
    }
  }
  int mid=(a+b)>>1;
  if(C>mid)eat(x<<1|1,mid+1,b);
  eat(x<<1,a,mid);
}
inline int lower(ll x){
  int l=1,r=m,t,mid;
  while(l<=r)if(e[mid=(l+r)>>1]>=x)r=(t=mid)-1;else l=mid+1;
  return t;
}
inline int query(ll A,ll B){
  int ans=0;
  cp=0;
  while(A<B){
    //>=A
    C=lower(A);
    NXT=0;
    getnxt(1,1,m);
    NXT=min(NXT,B-1);
    C--;
    SUM=A;
    CNT=0;
    //SUM>NXT
    eat(1,1,m);
    if(SUM<=NXT)return -1;
    A=SUM;
    ans+=CNT;
  }
  return ans;
}
int main(){
  scanf("%d",&n);
  e[ce=1]=0;
  for(i=1;i<=n;i++)scanf("%lld",&a[i]),e[++ce]=a[i];
  scanf("%d",&q);
  for(i=1;i<=q;i++){
    scanf("%lld%lld",&op[i][0],&op[i][1]);
    if(op[i][0]==1)scanf("%lld",&op[i][2]);
    if(op[i][0]==2)e[++ce]=op[i][1];
  }
  sort(e+1,e+ce+1);
  for(i=1;i<=ce;i++)if(i==1||e[i]>e[m])e[++m]=e[i];
  e[++m]=inf;
  have[m]=1;
  for(i=1;i<=n;i++)have[lower_bound(e+1,e+m+1,a[i])-e]++;
  build(1,1,m);
  for(i=1;i<=q;i++){
    POS++;
    if(op[i][0]==1){
      printf("%d\n",query(op[i][1],op[i][2]));
      while(cp){
        change(1,1,m,pool[cp][0],e[pool[cp][0]]*pool[cp][1],pool[cp][1]);
        cp--;
      }
    }
    if(op[i][0]==2)change(1,1,m,lower_bound(e+1,e+m+1,op[i][1])-e,op[i][1],1);
    if(op[i][0]==3)change(1,1,m,lower_bound(e+1,e+m+1,op[i][1])-e,-op[i][1],-1);
  }
}