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
#include <bits/stdc++.h>
using namespace std;
struct Node {
  int cnt,bc;
  long long sum,bs;
} c[1200200];
int n,m,num,i,nxt,res,q,qt[100100];
long long qai,bnxt,a[300300],b[400400],qa[100100],qb[100100];
void modify(long long x, int v) {
  int i=1,L=1,R=num;
  while (true) {
    c[i].cnt+=v;   c[i].bc=c[i].cnt;
    c[i].sum+=x*v; c[i].bs=c[i].sum;
    if (L==R) break;
    int h=(L+R)/2;
    i*=2;
    if (x>b[h]) {
      L=h+1;
      ++i;
    } else R=h;
  }
}
int findnext(int i, int L, int R, long long x) {
  if (L==R) return (b[R]>=x && c[i].cnt>0)?R:0;
  int h=(L+R)/2,res=0;
  if (x<=b[h]) res=findnext(i*2,L,h,x);
  if (res==0) return findnext(i*2+1,h+1,R,x);
  return res;
}
void collect(int i, int L, int R, long long x) {
  if (b[R]<x && qai+c[i].sum<=bnxt) {
    res+=c[i].cnt; c[i].cnt=0;
    qai+=c[i].sum; c[i].sum=0;
    return;
  }
  if (L==R) {
    if (b[R]>=x) return;
    long long z=min(1LL*c[i].cnt,(bnxt-qai)/b[R]+1);
    long long zs=z*b[R];
    res+=z;  c[i].cnt-=z;
    qai+=zs; c[i].sum-=zs;
    return;
  }
  int h=(L+R)/2;
  if (qai<=bnxt && b[h+1]<x) collect(i*2+1,h+1,R,x);
  if (qai<=bnxt) collect(i*2,L,h,x);
  c[i].cnt=c[i*2].cnt+c[i*2+1].cnt;
  c[i].sum=c[i*2].sum+c[i*2+1].sum;
}
void recover(int i, int L, int R) {
  if (c[i].sum!=c[i].bs) {
    c[i].cnt=c[i].bc;
    c[i].sum=c[i].bs;
  } else return;
  if (L==R) return;
  int h=(L+R)/2;
  recover(i*2,L,h);
  recover(i*2+1,h+1,R);
}
int main() {
  scanf("%d",&n);
  for (i=0; i<n; i++) {
    scanf("%lld",&a[i]);
    b[i+1]=a[i];
  }
  scanf("%d",&q); m=n;
  for (i=0; i<q; i++) {
    scanf("%d%lld",&qt[i],&qa[i]);
    if (qt[i]==1) scanf("%lld",&qb[i]);
    if (qt[i]==2) b[++m]=qa[i];
  }
  sort(b+1,b+m+1);
  for (num=0, i=1; i<=m; i++) if (num==0 || b[i]!=b[num]) b[++num]=b[i];
  for (i=0; i<n; i++) modify(a[i],1);
  for (i=0; i<q; i++) if (qt[i]==1) {
    for (res=0; qb[i]>qa[i]; ) {
      qai=qa[i];
      bnxt=qb[i]-1;
      nxt=findnext(1,1,num,qai);
      if (nxt!=0 && b[nxt]<bnxt) bnxt=b[nxt];
      collect(1,1,num,qa[i]);
      qa[i]=qai;
      if (qa[i]<=bnxt) break;
    }
    printf("%d\n",(qb[i]>qa[i])?-1:res);
    recover(1,1,num);
  } else modify(qa[i],(qt[i]==3)?-1:1);
  return 0;
}