80 pts！

#include<bits/stdc++.h>
using namespace std;
inline bool id(const char ch) {
	return ch>='0'&&ch<='9';
}
inline int read(void) {
	int s=0,f=0;
	char ch=getchar();
	while(!id(ch)) f=(ch=='-'),ch=getchar();
	while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return f?-s:s;
}
const int MAXN=5e4+10;
struct Fhq_Treap {
	int l,r,sze,key,val;	
};
int n,m,idx,a[MAXN];
struct Segment_Tree {
	int l,r,root=0,idx=0,A,B,C,D,ans;
	vector<Fhq_Treap> tr;
	inline void push_up(const int u) {
		return tr[u].sze=tr[tr[u].l].sze+tr[tr[u].r].sze+1,void();
	}
	inline void init(void) {
		return tr.push_back(Fhq_Treap{0,0,0,0,0}),void();	
	}
	inline int get_node(const int key) {
		return tr.push_back(Fhq_Treap{0,0,1,key,rand()}),++idx;	
	}
	inline void split(const int u,const int k,int &x,int &y) {
		if(u==0) return x=y=0,void();
		if(tr[u].key<=k) return x=u,split(tr[u].r,k,tr[u].r,y),push_up(u),void();
		return y=u,split(tr[u].l,k,x,tr[u].l),push_up(u),void();	
	}
	inline int merge(const int x,const int y) {
		if(!x||!y) return x|y;
		if(tr[x].val>=tr[y].val) return tr[x].r=merge(tr[x].r,y),push_up(x),x;
		return tr[y].l=merge(x,tr[y].l),push_up(y),y;
	}
	inline void insert(const int val) {
		return split(root,val,A,B),root=merge(merge(A,get_node(val)),B),void();
	}
	inline void remove(const int val) {
		return split(root,val-1,A,B),split(B,val,C,D),root=merge(merge(A,merge(tr[C].l,tr[C].r)),D),void();	
	}
	inline int rank(const int val) {
		return split(root,val-1,A,B),ans=tr[A].sze,root=merge(A,B),ans;
	}
	inline int get_mx(const int u,const int val) {
		if(!u) return -INT_MAX;
		if(tr[u].key>=val) return get_mx(tr[u].l,val);
		return max(tr[u].key,get_mx(tr[u].r,val));
	}
	inline int get_mn(const int u,const int val) {
		if(!u) return INT_MAX;
		if(tr[u].key<=val) return get_mn(tr[u].r,val);
		return min(tr[u].key,get_mn(tr[u].l,val));
	}
	inline int pre(const int val) {
		return get_mx(root,val);	
	}
	inline int nxt(const int val) {
		return get_mn(root,val);	
	}
}seg[MAXN<<2];
inline int build(const int l,const int r) {
	++idx,seg[idx].init(),seg[idx].insert(-INT_MAX),seg[idx].insert(INT_MAX);
	for(register int i=l;i<=r;i++) seg[idx].insert(a[i]);
	if(l==r) return idx;
	int mid=l+r>>1,k=idx;
	seg[k].l=build(l,mid),seg[k].r=build(mid+1,r);
	return k;
}
inline void update(const int k,const int l,const int r,const int x,const int val) {
	seg[k].insert(val),seg[k].remove(a[x]);
	if(l==r) return ;
	int mid=l+r>>1;
	if(x<=mid) update(seg[k].l,l,mid,x,val);
	else update(seg[k].r,mid+1,r,x,val);
	return ;
}
inline int query_rank(const int k,const int l,const int r,const int x,const int y,const int val) {
	if(x<=l&&r<=y) return seg[k].rank(val)-1;
	int mid=l+r>>1,ans=0;
	if(x<=mid) ans+=query_rank(seg[k].l,l,mid,x,y,val);
	if(y>mid) ans+=query_rank(seg[k].r,mid+1,r,x,y,val);
	return ans;
}
inline int query_sum(const int L,const int R,const int val) {
	int l=0,r=100000000,mid,ans;
	while(l<=r) {
		mid=l+r>>1;
		if(query_rank(1,1,n,L,R,mid)+1<=val) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
inline int query_pre(const int k,const int l,const int r,const int x,const int y,const int val) {
	if(x<=l&&r<=y) return seg[k].pre(val);
	int mid=l+r>>1,ans=-INT_MAX;
	if(x<=mid) ans=max(ans,query_pre(seg[k].l,l,mid,x,y,val));
	if(y>mid) ans=max(ans,query_pre(seg[k].r,mid+1,r,x,y,val));
	return ans;
}
inline int query_nxt(const int k,const int l,const int r,const int x,const int y,const int val) {
	if(x<=l&&r<=y) return seg[k].nxt(val);
	int mid=l+r>>1,ans=INT_MAX;
	if(x<=mid) ans=min(ans,query_nxt(seg[k].l,l,mid,x,y,val));
	if(y>mid) ans=min(ans,query_nxt(seg[k].r,mid+1,r,x,y,val));
	return ans;
}
int main() {
//	cout<<"WULA!\n";
	n=read(),m=read();
	for(register int i=1;i<=n;++i) a[i]=read();
	build(1,n);
//	cout<<"WULA!\n";
	for(register int i=1,op,l,r,k;i<=m;++i) {
		op=read();
		if(op==1) l=read(),r=read(),k=read(),printf("%d\n",query_rank(1,1,n,l,r,k)+1);
		if(op==2) l=read(),r=read(),k=read(),printf("%d\n",query_sum(l,r,k));
		if(op==3) l=read(),k=read(),update(1,1,n,l,k),a[l]=k;
		if(op==4) l=read(),r=read(),k=read(),printf("%d\n",query_pre(1,1,n,l,r,k));
		if(op==5) l=read(),r=read(),k=read(),printf("%d\n",query_nxt(1,1,n,l,r,k));
	}
	return 0;	
}