#include<bits/stdc++.h>
using namespace std;
long long n,m,a[4000100],tree[10010],u,l,q,p,r;
void put(long long i){
    bool flag=1;
    m++;
    for(int x=1;x<m;x++){
        if(a[tree[x]]>a[i]){
            flag=0;
            for(int y=m;y>x;y--){
                tree[y]=tree[y-1];
            }
            tree[x]=i;
            break;
        }
    }
    if(flag){
        tree[m]=i;
    }
}
void find(long long i,long long j){
    long long t,e=m;
    for(int x=1;x<=m;x++){
        if(a[tree[x]]>=i){
            t=x;
            break;
        }
    }
    if(t==0){
        t=m;
    }
    for(int x=m;x>t;x--){
        if(a[tree[x]]<=j){
            e=x;
            break;
        }
    }
    cout<<e-t+1<<endl;
    return;
}
void chang(long long i){
    bool flag=1;
    for(int x=1;x<m;x++){
        if(x==i){
            continue;
        }
        if(tree[x]>a[i]){
            if(x<i){
                for(int y=x+1;y<=i;y++){
                    tree[y]=tree[y-1];
                }
                tree[x]=i;
            }
            else{
                for(int y=x-1;y>=i;y++){
                    tree[y]=tree[y+1];
                }
                tree[x]=i;
            }
            flag=0;
            break;
        }
    }
    if(flag){
        for(int x=m-1;x>=i;x++){
            tree[x]=tree[x+1];
        }
        tree[m]=i;
    }
    return;
}
int main(){
    freopen("hjtree.in","r",stdin);
    freopen("hjtree.out","w",stdout);
    cin>>n;
    for(int x=1;x<=n;x++){
        cin>>a[x];
        cout<<x<<endl;
        put(x);
    }
    for(int x=1;x<n;x++){
        cin>>q;
        cin>>q;
    }
    cin>>u;
    for(int x=1;x<=u;x++){
        cin>>l;
        if(l==1){
            cin>>q>>p;
            cout<<a[tree[p]]<<endl;
        }
        else if(l==2){
            cin>>q>>p>>r;
            if(p>r){
                swap(p,r);
            }
            find(p,r);
        }
        else{
            cin>>q>>p;
            a[q]=p;
            chang(q);
        }
    }
    return 0;
}