#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
inline int rd(){
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar(); 
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*f;
}
inline void out(int x){
	if(x>9) out(x/10);
	putchar('0'+x%10);
	return ;
}
gp_hash_table<int,int> mp;
int const X=1e5+100;
int n,Q,a[X],sq,op,qnum,cnum,ans[X],gp;
int cnt[X],tt[X];
struct change{
	int pos,val;
};
change c[X];
struct query{
	int l,r,id,pre;
	bool operator<(const query &o)const{
		return (o.l/sq)==(l/sq)?(o.r/sq)<(r/sq):(o.l/sq)<(l/sq);
	}
};
query q[X];
inline void del(int x){
	tt[cnt[x]]--;
	cnt[x]--;
	tt[cnt[x]]++;
	return ;
}
inline void add(int x){
	tt[cnt[x]]--;
	cnt[x]++;
	tt[cnt[x]]++;
	return ;
}
inline void work(int now,int i){
	if(q[i].l<=c[now].pos&&c[now].pos<=q[i].r){
		tt[cnt[c[now].val]]--; tt[cnt[a[c[now].pos]]]--;
		cnt[c[now].val]++;
		cnt[a[c[now].pos]]--;
		tt[cnt[c[now].val]]++; tt[cnt[a[c[now].pos]]]++;
	}
	swap(c[now].val,a[c[now].pos]);
	return ;
}
inline int mex(){ //暴力求mex 
	int o=1;
	while(tt[o]) o++;
	return o;
}
inline void modui(){
	int l=1,r=0,now=0;
	for(int i=1;i<=qnum;i++){
		while(l<q[i].l) del(a[l++]);
		while(l>q[i].l) add(a[--l]);
		while(r<q[i].r) add(a[++r]);
		while(r>q[i].r) del(a[r--]);
		while(now<q[i].pre) work(++now,i);
		while(now>q[i].pre) work(now--,i);
		ans[q[i].id]=mex();
	}
	return ;
}
int main() {
	n=rd(); Q=rd();
	//cout<<n;
	sq=sqrt(n);
	for(int i=1;i<=n;i++){
		a[i]=rd();
		//离散化 
		if(mp.find(a[i])!=mp.end()){
			a[i]=mp[a[i]];
		}
		else{
			mp[a[i]]=++gp;
			a[i]=gp;
		}
	}
	for(int i=1;i<=Q;i++){
		op=rd();
		if(op==1){
			q[++qnum].id=qnum;
			q[qnum].l=rd(); q[qnum].r=rd();
			q[qnum].pre=cnum;
		}
		else{
			c[++cnum].pos=rd();
			c[cnum].val=rd();
			if(mp.find(c[cnum].val)!=mp.end()){
				c[cnum].val=mp[c[cnum].val];
			}
			else{
				mp[c[cnum].val]=++gp;
				c[cnum].val=gp;
			}
		}
	}
	sort(q+1,q+1+qnum);
	modui();
	for(int i=1;i<=qnum;i++){
		out(ans[i]);
		putchar('\n');
	}
	return 0;
}

感谢.jpg