#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
inline int read(){
    int w=0,x=0;char ch;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();};
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return w?-x:x;
}
int n,m;
int size[10000005],ch[10000005][5],val[10000005];
int dat[10000005];
int a[500015];
int tot;
struct fhq_treap{
    int root;
    inline void pushup(int p){  
        size[p]=size[ch[p][0]]+size[ch[p][1]]+1;
    }
    inline int New(int k){ 
        val[++tot]=k;  
        dat[tot]=rand();  
        size[tot]=1;  
        return tot; 
    }
    inline void split(int p,int k,int &x,int &y){
        if(p==0){
            x=y=0;  
            return ;
        }
        if(val[p]<=k){ //val[p]<=k
            x=p; 
            split(ch[p][1],k,ch[p][1],y);
        }
        else{
            y=p;  
            split(ch[p][0],k,x,ch[p][0]);
        }
        pushup(p);
    }
    inline int merge(int x,int y){ 
        if(!x||!y) return x+y; 
        if(dat[x]<dat[y]){ 
            ch[x][1]=merge(ch[x][1],y);
            pushup(x);  
            return x;  
        }
        else{
            ch[y][0]=merge(x,ch[y][0]); 
            pushup(y);
            return y; 
        }
    }
    int x,y,z;
    inline void insert(int k){
        split(root,k,x,y); 
        root=merge(merge(x,New(k)),y);
    }
    inline void del(int k){
        split(root,k,x,z);
        split(x,k-1,x,y);
        y=merge(ch[y][0],ch[y][1]); 
        root=merge(merge(x,y),z); 
    }
    inline int getrank(int k){
        split(root,k-1,x,y); 
        int ans=size[x]+1;
        root=merge(x,y); 
        return ans;
    }
    inline int getval(int p,int k){
        if(k<=size[ch[p][0]]) return getval(ch[p][0],k);
        if(k==size[ch[p][0]]+1) return val[p];
        return getval(ch[p][1],k-size[ch[p][0]]-1);
    }
    inline int getbef(int k){
        split(root,k-1,x,y);
        register int ans=0;
        if(size[x]) ans=getval(x,size[x]);
        else ans=-INF;
        root=merge(x,y);
        return ans;
    }
    inline int getaft(int k){
        split(root,k,x,y);
        register int ans=0;
        if(size[y]) ans=getval(y,1);
        else ans=INF;
        root=merge(x,y);
        return ans;
    }
    inline void build(int l,int r){
        for(register int i=l;i<=r;++i){
            insert(a[i]);
        }
    }
}treap[500015];
struct segment_tree{
    int root[500015];
    inline void build(int p,int l,int r){
        treap[p].build(l,r);
        if(l==r) return ;
        register int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
    }
    inline void change(int p,int l,int r,int k,int v){
        treap[p].del(a[k]);
        treap[p].insert(v);
        if(l==r) return ;
        register int mid=(l+r)>>1;
        if(k<=mid) change(p<<1,l,mid,k,v);
        else change(p<<1|1,mid+1,r,k,v);
    }
    inline int getrank(int p,int x,int y,int l,int r,int k){
        if(y<l||r<x) return 0;
        if(l<=x&&y<=r){
            return treap[p].getrank(k)-1;
        }
        register int mid=(x+y)>>1;
        return getrank(p<<1,x,mid,l,r,k)+getrank(p<<1|1,mid+1,y,l,r,k);
    }
    inline int getval(int x,int y,int k){
        register int l=0,r=1e8;
        register int ans=-1;
        while(l<=r){
            if(getrank(1,1,n,x,y,(l+r)>>1)+1<=k){
                register int mid=(l+r)>>1;
                ans=mid,l=mid+1;
            }
            else r=((l+r)>>1)-1;
        }
        return ans;
    }
    inline int getbef(int p,int x,int y,int l,int r,int k){
        if(x>r||y<l) return -INF;
        if(l<=x&&y<=r){
            return treap[p].getbef(k);
        }
        register int mid=(x+y)>>1;
        return max(getbef(p<<1,x,mid,l,r,k),getbef(p<<1|1,mid+1,y,l,r,k));
    }
    inline int getaft(int p,int x,int y,int l,int r,int k){
        if(x>r||y<l) return INF;
        if(l<=x&&y<=r){
            return treap[p].getaft(k);
        }
        register int mid=(x+y)>>1;
        return min(getaft(p<<1,x,mid,l,r,k),getaft(p<<1|1,mid+1,y,l,r,k));
    }
}segmental_tree;
int opt,g,h,ph;
int main(){
    srand(112358);
    n=read(),m=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
    }
    segmental_tree.build(1,1,n);
    for(register int i=1;i<=m;++i){
        opt=read(),g=read(),h=read();
        if(opt==1) ph=read(),printf("%d\n",segmental_tree.getrank(1,1,n,g,h,ph)+1);
        if(opt==2) ph=read(),printf("%d\n",segmental_tree.getval(g,h,ph));
        if(opt==3) segmental_tree.change(1,1,n,g,h),a[g]=h;
        if(opt==4) ph=read(),printf("%d\n",segmental_tree.getbef(1,1,n,g,h,ph));
        if(opt==5) ph=read(),printf("%d\n",segmental_tree.getaft(1,1,n,g,h,ph));
    }
    return 0;
}