#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=400005;
int n,q,tot,ans[N],a[N],bl[N],block,st[N],mp[N],mpp[N];
unordered_map<int,int> lsh;
struct node{
	int l,r,t,id;
}qu[N];
struct chang{
	int x,y;
}ch[N];
bool cmp(node x,node y){
	if(bl[x.l]!=bl[y.l]) return bl[x.l]<bl[y.l];
	if(bl[x.r]!=bl[y.r]) return bl[x.r]<bl[y.r];
	return x.t<y.t;
}
void add(int x){
	mpp[mp[a[x]]]--;
	mp[a[x]]++;
	mpp[mp[a[x]]]++;
}
void del(int x){
	mpp[mp[a[x]]]--;
	mp[a[x]]--;
	mpp[mp[a[x]]]++;
}
void change(int i,int x,int y,int l,int r){
	if(x>=l&&x<=r) del(x);
	swap(ch[i].y,a[x]);
	if(x>=l&&x<=r) add(x);
}
signed main(){
	cin>>n>>q;
	block=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		bl[i]=(i-1)/block+1;
		if(bl[i]!=bl[i-1]) st[bl[i]]=i;
		if(!lsh[a[i]]) lsh[a[i]]=++tot;
		a[i]=lsh[a[i]];
	}
	bl[n+1]=bl[n]+1;
	st[bl[n+1]]=n+1;
	int cnt1=0,cnt2=0;
	for(int i=1;i<=q;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1) qu[++cnt1]={x,y,cnt2,cnt1};
		else{
			if(!lsh[y]) lsh[y]=++tot;
			y=lsh[y];
			ch[++cnt2]={x,y};
		}
	}
	sort(qu+1,qu+1+cnt1,cmp);
	int l=qu[1].l,r=l-1,t=0;
	for(int i=1;i<=cnt1;i++){
		while(l<qu[i].l) del(l),l++;
		while(l>qu[i].l) l--,add(l);
		while(r>qu[i].r) del(r),r--;
		while(r<qu[i].r) r++,add(r);
		while(t<qu[i].t) t++,change(t,ch[t].x,ch[t].y,l,r);
		while(t>qu[i].t) change(t,ch[t].x,ch[t].y,l,r),t--;
		int j=1;
		while(j++){
			if(mpp[j]) continue;
			ans[qu[i].id]=j;
			break;
		}
	}
	for(int i=1;i<=cnt1;i++) cout<<ans[i]<<endl;
	return 0;
}
/*
发现最多只有根号个答案，直接暴力就完了
*/