C++ :

#include<bits/stdc++.h>
#define lb lower_bound
using namespace std;
const int N=50005;
int d[N],m,n,p,s,t,v;
typedef vector<int>vec;
vec a[N];
void ins(vec&a,int v){a.insert(lb(a.begin(),a.end(),v),v);}
void del(vec&a,int v){a.erase(lb(a.begin(),a.end(),v));}
void ins(int i,int v){for(;i<=n;i+=i&-i)ins(a[i],v);}
void del(int i,int v){for(;i<=n;i+=i&-i)del(a[i],v);}
int ask(vec&a,int v){return lb(a.begin(),a.end(),v)-a.begin();}
int ask(int v,int s,int t){
	int k=1;
	for(;s;s^=s&-s)k-=ask(a[s],v);
	for(;t;t^=t&-t)k+=ask(a[t],v);
	return k;
}
int cal(int v,int s,int t){
	int l=0,r=1e8;
	while(l^r){int j=l+r+1>>1;v>=ask(j,s,t)?l=j:r=j-1;}
	return l;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",d+i),ins(i,d[i]);
	while(m--){
		scanf("%d%d%d",&p,&s,&t);
		if(p==3){del(s,d[s]),ins(s,d[s]=t);continue;}
		--s,scanf("%d",&v);
		if(p==1)
			printf("%d\n",ask(v,s,t));
		if(p==2)
			printf("%d\n",cal(v,s,t));
		if(p==4)
			printf("%d\n",cal(ask(v,s,t)-1,s,t));
		if(p==5)
			printf("%d\n",cal(ask(v+1,s,t),s,t));
	}
}