#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=;

 struct query{

     int x,y,type,k,w;

 }q[N],c1[N],c2[N];

 int n,m,ans[N],tr[N],mx,tot,cnt,a[N];

 int lowbit(int x){

     return x&-x;

 }

 void add(int x,int w){

     for(int i=x;i<=n;i+=lowbit(i)){

         tr[i]+=w;

     }

 }

 int getsum(int x){

     int ans=;

     for(int i=x;i;i-=lowbit(i)){

         ans+=tr[i];

     }

     return ans;

 }

 void solve(int l,int r,int L,int R){

     if(l>r)return;

     if(L==R){

         for(int i=l;i<=r;i++){

             if(q[i].type==)ans[q[i].w]=L;

         }

         return ;

     }

     int mid=(L+R)>>;

     int lnow=;int rnow=;

     for(int i=l;i<=r;i++){

         if(q[i].type==){

             int tmp=getsum(q[i].y)-getsum(q[i].x-);

             if(tmp>=q[i].k){

                 c1[++lnow]=q[i];

             }

             else{

                 q[i].k-=tmp;

                 c2[++rnow]=q[i];

             }

         }

         else{

             if(q[i].type==&&q[i].y<=mid)add(q[i].x,);

             if(q[i].type==&&q[i].y<=mid)add(q[i].x,-);

             if(q[i].y<=mid)c1[++lnow]=q[i];

             else c2[++rnow]=q[i];

         }

     }

     for(int i=l;i<=r;i++){

         if(q[i].type==&&q[i].y<=mid)add(q[i].x,-);

         if(q[i].type==&&q[i].y<=mid)add(q[i].x,);

     }

     for(int i=;i<=lnow;i++){

         q[l+i-]=c1[i];

     }

     for(int i=;i<=rnow;i++){

         q[l+lnow+i-]=c2[i];

     }

     solve(l,l+lnow-,L,mid);

     solve(l+lnow,r,mid+,R);

 }

 int main(){

     while(~scanf("%d",&n)){

         mx=;cnt=;tot=;

         for(int i=;i<=n;i++){

             scanf("%d",&a[i]);

             q[++cnt].type=;q[cnt].x=i;q[cnt].y=a[i];

             mx=max(mx,a[i]);

         }

         scanf("%d",&m);

         for(int i=;i<=m;i++){

             int k;

             scanf("%d",&k);

             if(k==){

                 int x,y;

                 scanf("%d%d",&x,&y);

                 q[++cnt].type=;q[cnt].x=x;q[cnt].y=a[x];

                 q[++cnt].type=;q[cnt].x=x;q[cnt].y=y;

                 a[x]=y;

                 mx=max(mx,y);

             }

             else{

                 int x,y,k;

                 scanf("%d%d%d",&x,&y,&k);

                 q[++cnt].type=;q[cnt].x=x;q[cnt].y=y;q[cnt].k=k;

                 q[cnt].w=++tot;

             }

         }

         solve(,cnt,,mx);

         for(int i=;i<=tot;i++){

             printf("%d\n",ans[i]);

         }

     }

     return ;

 }