已经试过把 get_next 和 get_prev 改成递归了，没用

#include<cstdio>
#include<random>
using namespace std;
const int MAXN=5e5+10;
mt19937 rnd(114514);
int a[MAXN];
int n,m;
inline int max(int H,int G){
	return H>G?H:G;
}
inline int min(int H,int G){
	return H<G?H:G;
}
struct TREAP{
	struct TREENODE{
		int lson;
		int rson;
		int size_subtree;
		int dat,val;
		TREENODE(){
			lson=rson=0;
		}
	}tr[MAXN<<5];
	#define ls(u) tr[u].lson
	#define rs(u) tr[u].rson
	int tot=0;
	void New(int val){
		tr[++tot].val=val;
		tr[tot].dat=rnd();
		tr[tot].size_subtree=1;
	}
	inline void pushup(int &u){
		tr[u].size_subtree=tr[ls(u)].size_subtree+tr[rs(u)].size_subtree+1;
	}
	void Split(int u,int val,int &L,int &R){
		if(u==0){
			L=R=0;
			return;
		}
		if(tr[u].val<=val){
			L=u;
			Split(rs(L),val,rs(L),R);
		}
		else{
			R=u;
			Split(ls(R),val,L,ls(R));
		}
		pushup(u);
	}
	int Merge(int L,int R){
		if(L==0||R==0){
			return L|R;
		}
		if(tr[L].dat>tr[R].dat){
			rs(L)=Merge(rs(L),R);
			pushup(L);
			return L;
		}
		else{
			ls(R)=Merge(L,ls(R));
			pushup(R);
			return R;
		}
	}
	void Insert(int &rot,int val){
		int L,R;
		Split(rot,val,L,R);
		New(val);
		rot=Merge(Merge(L,tot),R);
	}
	void Delete(int &rot,int val){
		int L,R,p;
		Split(rot,val,L,R);
		Split(L,val-1,L,p);
		p=Merge(ls(p),rs(p));
		rot=Merge(Merge(L,p),R);
	}
	int get_rank(int &rot,int val){
		int L,R;
		Split(rot,val-1,L,R);
		int res=tr[L].size_subtree-1;
		rot=Merge(L,R);
		return res;	
	}
	int get_value(int u,int rk){
		if(rk==tr[ls(u)].size_subtree+1){
			return u;
		}
		else if(rk>tr[ls(u)].size_subtree+1){
			return get_value(rs(u),rk-tr[ls(u)].size_subtree-1);
		}
		else{
			return get_value(ls(u),rk);
		}
	}
	int get_prev(int &rot,int val){
		int L,R;
		Split(rot,val-1,L,R);
		int res=tr[get_value(L,tr[L].size_subtree)].val;
		rot=Merge(L,R);
		return res;
	}
	int get_next(int &rot,int val){
		int L,R;
		Split(rot,val,L,R);
		int res=tr[get_value(R,1)].val;
		rot=Merge(L,R);
		return res;
	}
	#undef ls
	#undef rs
}Treap;
struct SegmentTree{
	int root[MAXN<<2];
	#define ls rt<<1
	#define rs (rt<<1)|1
	#define lson l,mid,rt<<1
	#define rson mid+1,r,(rt<<1)|1
	void build(int l,int r,int rt){
		Treap.Insert(root[rt],-2147483647);
		for(int i=l;i<=r;++i){
			Treap.Insert(root[rt],a[i]);
		}
		Treap.Insert(root[rt],2147483647);
		if(l==r){
			return;
		}
		int mid=(l+r)>>1;
		build(lson);
		build(rson);
	}
	void update(int pos,int val,int l,int r,int rt){
		Treap.Delete(root[rt],a[pos]);
		Treap.Insert(root[rt],val);
		if(l==r){
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid){
			update(pos,val,lson);
		}
		else{
			update(pos,val,rson);
		}
	}
	int get_rank(int L,int R,int val,int l,int r,int rt){
		if(L<=l&&r<=R){
			return Treap.get_rank(root[rt],val);
		}
		int mid=(l+r)>>1;
		if(R<=mid){
			return get_rank(L,R,val,lson);
		}
		if(L>mid){
			return get_rank(L,R,val,rson);
		}
		return get_rank(L,R,val,lson)+get_rank(L,R,val,rson);
	}
	int get_value(int L,int R,int rk){
		int l=0,r=1e8;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(get_rank(L,R,mid,1,n,1)<rk){
				l=mid;
			}
			else{
				r=mid-1;
			}
		}
		return r;
	}
	int get_prev(int L,int R,int val,int l,int r,int rt){
		if(l>R||r<L){
			return -2147483647;
		}
		else if(L<=l&&r<=R){
			return Treap.get_prev(root[rt],val);
		}
		else{
			int mid=(l+r)>>1;
			return max(get_prev(L,R,val,lson),get_prev(L,R,val,rson));
		}
	}
	int get_next(int L,int R,int val,int l,int r,int rt){
		if(l>R||r<L){
			return 2147483647;
		}
		else if(L<=l&&r<=R){
			return Treap.get_next(root[rt],val);
		}
		else{
			int mid=(l+r)>>1;
			return min(get_next(L,R,val,lson),get_next(L,R,val,rson));
		}
	}
	#undef ls
	#undef rs
	#undef lson
	#undef rson
}T;
char *p1,*p2,buf[MAXN];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
inline void read(int &x){
	char c;
	c=gc();
	while(c<'0'||c>'9'){
		c=gc();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+(c&15);
		c=gc();
	}
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	T.build(1,n,1);
	for(int kkk=1,op,x,y,k;kkk<=m;++kkk){
		scanf("%d%d%d",&op,&x,&y);
		if(op==3){
			T.update(x,y,1,n,1);
			a[x]=y;
		}
		else{
			scanf("%d",&k);
			switch(op){
				case 1:{
					printf("%d\n",T.get_rank(x,y,k,1,n,1)+1);
					break;
				}
				case 2:{
					printf("%d\n",T.get_value(x,y,k));
					break;
				}
				case 4:{
					printf("%d\n",T.get_prev(x,y,k,1,n,1));
					break;
				}
				case 5:{
					printf("%d\n",T.get_next(x,y,k,1,n,1));
					break;
				}
			}
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}