Rt

#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int l,r;
	int id;
	int t;
}a[900010];
int n,m,k;
struct node2
{
	int pos,val;
}C[100010];
int cnt[900010];
int pos[900010];
int tot[100010];
int sum;
int t;
int c[190010];
void add(int col)
{
	--tot[cnt[col]];
	++tot[++cnt[col]];
}
void cel(int col)
{
	--tot[cnt[col]];
	++tot[--cnt[col]];
}
void work(int ti,int qu)
{
	if(C[ti].pos>=a[qu].l&&C[ti].pos<=a[qu].r)
	{
		cel(c[C[ti].pos]);
		add(C[ti].val);
	}
	swap(C[ti].val,c[C[ti].pos]);
}
bool cmp(node a,node b)
{
	return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9)
    {
    	write(x/10);
	}
    putchar(x%10+'0');
}
inline int read() 
{
     bool f=false; 
	 int x=0;
     char ch=getchar();
     while(ch<'0'||ch>'9') 
	 {
         if(ch=='-') 
		 {
		 	f=true;
		 }
         ch=getchar();
     }
     while(ch>='0'&&ch<='9') 
	 {
         x=(x<<1)+(x<<3)+ch-'0';
         ch=getchar();
     }
     return f?-x:x;
 }
int ans[100010],b[1000010];
signed main()
{
	int i,j;
	n=read(),m=read();
	int log=1;
	t=pow(n,2.0/3);
	for(i=1;i<=n;++i)
		c[i]=read(),pos[i]=(i+t-1)/t,b[log++]=c[i];
	//for(int i=1;i<=n;i++)
	//	add(c[i]);
	int qnum=0,cnum=0;
	for(i=1;i<=m;++i)
	{
		char op;
		op=getchar();
		int l,r;
		l=read(),r=read();
		if(op=='1')
		{
			a[++qnum].l=l,a[qnum].r=r;
			a[qnum].id=qnum,a[qnum].t=cnum;
			
		}
		else
			C[++cnum].pos=l,C[cnum].val=r,b[log++]=r;
	}
	sort(b+1,b+log+1);
	log=unique(b,b+log)-b-1;
	for(i=1;i<=n;++i)
		c[i]=lower_bound(b+1,b+log+1,c[i])-b;
	for(i=1;i<=cnum;++i)
		C[i].val=lower_bound(b+1,b+log+1,C[i].val)-b;
	sort(a+1,a+qnum+1,cmp);
	int l=1,r=0,now=0;
	for(i=1;i<=qnum;++i)
	{
		while(l<a[i].l)cel(c[l++]);
		while(l>a[i].l)add(c[--l]);
		while(r<a[i].r)add(c[++r]);
		while(r>a[i].r)cel(c[r--]);
		while(now<a[i].t)work(++now,i);
		while(now>a[i].t)work(now--,i);
		for(ans[a[i].id]=1;tot[ans[a[i].id]]>0;ans[a[i].id]++);
	}
	for(i=1;i<=qnum;++i)
	{	
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}