总有一两个点会略大或略小

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define R(x) x = read()
#define int long long
#define mp make_pair
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
struct rbt{
	using pii=pair<int,int>; 
	tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> t;
	void insert(pii a){
		t.insert(a);
	}
	void erase(pii a){
		t.erase(a);
	}
	pii begin(){
		return *t.begin();
	}
	void chng(int pos,int k){
		t.erase(t.upper_bound(mp(0,pos)));
		t.insert(mp(k,pos));
	}
	bool empty(){
		return t.empty();
	}
	int size(){
		return t.size();
	}
	int pre(int x){
		auto it=t.upper_bound(mp(x,-2147483647));
		if(it==t.begin())return -2147483647;
		it--;
		return it->first;
	}
	int nxt(int x){
		auto it=t.upper_bound(mp(x,2147483647));
		if(it==t.end())return 2147483647;
		return it->first;
	}
	int rank(int x){
		return t.order_of_key(mp(x,0));
	}
};
rbt mrg(rbt x,rbt y){
	if(x.size()<y.size())swap(x,y);
	while(!y.empty()){
		x.insert(y.begin());
		y.erase(y.begin());
	}
	return x;
}
int n,m,a[50010];
struct node{
	int ls,rs;
	rbt s;
}t[400010];
int siz;
void new_node(int &i){i=++siz;}
void build(int i,int l,int r){
	if(l==r){
		t[i].s.insert(mp(a[l],l));
		return;
	}
	int mid=(l+r)>>1;
	new_node(t[i].ls);
	build(t[i].ls,l,mid);
	new_node(t[i].rs);
	build(t[i].rs,mid+1,r);
	t[i].s=mrg(t[t[i].ls].s,t[t[i].rs].s);
}
int opt,l,r,k;
int rnk(int i,int l,int r,int ll,int rr,int x){
	if(ll<=l&&r<=rr){
		return t[i].s.rank(x);
	}
	int mid=(l+r)>>1,res=0;
	if(ll<=mid)res+=rnk(t[i].ls,l,mid,ll,rr,x);
	if(rr>mid)res+=rnk(t[i].rs,mid+1,r,ll,rr,x);
	return res;
}
int kvl(int ll,int rr,int x){
	int l=0,r=1e8;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(rnk(1,1,n,ll,rr,mid)<=1+x){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	return r;
}
void motify(int i,int l,int r,int pos,int k){
	t[i].s.chng(pos,k);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(pos<=mid)motify(t[i].ls,l,mid,pos,k);
	else motify(t[i].rs,mid+1,r,pos,k);
}
int pre(int i,int l,int r,int ll,int rr,int x){
	if(ll<=l&&r<=rr){
		return t[i].s.pre(x);
	}
	int res=-2147483647;
	int mid=(l+r)>>1;
	if(ll<=mid)res=max(res,pre(t[i].ls,l,mid,ll,rr,x));
	if(rr>mid)res=max(res,pre(t[i].rs,mid+1,r,ll,rr,x));
	return res;
}
int nxt(int i,int l,int r,int ll,int rr,int x){
	if(ll<=l&&r<=rr){
		return t[i].s.nxt(x);
	}
	int res=2147483647;
	int mid=(l+r)>>1;
	if(ll<=mid)res=min(res,nxt(t[i].ls,l,mid,ll,rr,x));
	if(rr>mid)res=min(res,nxt(t[i].rs,mid+1,r,ll,rr,x));
	return res;
}
signed main(){
//	freopen("P3380_1.in","r",stdin);
//	freopen("OUT.out","w",stdout);
	R(n);R(m);
	for(int i=1;i<=n;i++)R(a[i]);
	new_node(siz);
	build(1,1,n);
	while(m--){
		R(opt);R(l);R(r);
		if(opt!=3)R(k);
		switch(opt){
			case 1:{
				write(rnk(1,1,n,l,r,k)+1);
				break;
			}
			case 2:{
				write(kvl(l,r,k));
				break;
			}
			case 3:{
				motify(1,1,n,l,r);
				break;
			}
			case 4:{
				write(pre(1,1,n,l,r,k));
				break;
			}
			case 5:{
				write(nxt(1,1,n,l,r,k));
				break;
			}
		}
		if(opt!=3)push('\n');
	}
    return 0;
}