#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m,bl,a[N],ans[N],cnt[N*2],tmp,c,t[N*2],ct,bz[N*2],op,b[N*2];
inline int read(){
    int x=0;
    bool f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=0;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f?x:-x;
}
struct Q{
	int l;
	int r;
	int id;
	int pre;
}q[N];
struct C{
	int pos;
	int val;
}ch[N]; 
bool cmp(Q x,Q y){
	return b[x.l] == b[y.l] ? x.r < y.r : x.l < y.l;
}
void work(int x,int i){
	if(ch[x].pos>=q[i].l&&ch[x].pos<=q[i].r){
		bz[cnt[a[ch[x].pos]]]--;
		cnt[a[ch[x].pos]]--;
		bz[cnt[a[ch[x].pos]]]++;
		bz[cnt[ch[x].val]]--;
		cnt[ch[x].val]++;
		bz[cnt[ch[x].val]]++;
	} 
	swap(a[ch[x].pos],ch[x].val);
}
void add(int x){
	bz[cnt[a[x]]]--;
	cnt[a[x]]++;
	bz[cnt[a[x]]]++;
}
void del(int x){
	bz[cnt[a[x]]]--;
	cnt[a[x]]--;
	bz[cnt[a[x]]]++;
}
int main(){
    ios::sync_with_stdio(false);
	n=read();
	m=read();
	bl=cbrt((double)n*n)+ 1;
	for(int i=1;i<=n;i++){
		b[i]=(i-1)/bl;
	}
	for(int i=1;i<=n;i++){
		a[i]=read();
		t[++ct]=a[i];
	}
	for(int i=1;i<=m;i++){
		op=read();
		if(op==2){
			tmp++;
			ch[tmp].pos=read();
			ch[tmp].val=read();
			t[++ct]=ch[tmp].val;
		}
		else{
			c++;
			q[c].l=read();
			q[c].r=read();
			q[c].id=c;
			q[c].pre=tmp;
		}
	}
	sort(t+1,t+ct+1);
	int tt = unique(t+1,t+ct+1)-t-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(t+1,t+tt+1,a[i])-t;
	for(int i=1;i<=tmp;i++) ch[i].val=lower_bound(t+1,t+tt+1,ch[i].val)-t;
	sort(q+1,q+c+1,cmp); 
	int L=1,R=0,now=0;
	for(int i=1;i<=c;i++){
		while(L>q[i].l) add(--L);
		while(R<q[i].r) add(++R);
		while(L<q[i].l) del(L++);
		while(R>q[i].r) del(R--);
		while(now<q[i].pre) work(++now,i);
		while(now>q[i].pre) work(now--,i);
		for(int j=1;;j++){
			if(bz[j]==0){
				ans[q[i].id]=j;
				break;
			}
		}
	}
	for(int i=1;i<=c;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}