// LUOGU_RID: 166250870
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,ubuf[1<<23],*u=ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
	TP x=0;
	int f=0;
	char ch=getchar();
	while(ch<48||ch>57) f|=ch=='-',ch=getchar();
	while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
	(read(args),...);
}
template<typename TP> inline void write(TP x)
{
	(x<0)?(putchar('-'),x=-x):0;
	(x>9)?(write(x/10),0):0;
	putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
	write<TP>(x);
	puts("");
}
int n,q,a[200001],opt,qcnt,mcnt,ans[200001],cnt[200001],cntcnt[200001];
__gnu_pbds::gp_hash_table<int,int> mp;
bitset<200001> mex;
struct queries
{
	int l,r,t,id;
} qrs[200001];
struct modifies
{
	int pos,val;
} mdf[200001];
inline void ers(int x)
{
//	if(!(--cntcnt[--cnt[x]])) mex[cnt[x]]=1;
	--cntcnt[cnt[x]];
	if(!cntcnt[cnt[x]]) mex[cnt[x]]=1;
	--cnt[x];
	if(!cntcnt[cnt[x]]) mex[cnt[x]]=0;
	++cntcnt[cnt[x]];
}
inline void epl(int x)
{
//	if(!(cntcnt[++cnt[x]]++)) mex[cnt[x]]=0;
	--cntcnt[cnt[x]];
	if(!cntcnt[cnt[x]]) mex[cnt[x]]=1;
	++cnt[x];
	if(!cntcnt[cnt[x]]) mex[cnt[x]]=0;
	++cntcnt[cnt[x]];
}
inline void cgt(int qid,int tim)
{
	if(qrs[qid].l<=mdf[tim].pos&&mdf[tim].pos<=qrs[qid].r) ers(a[mdf[tim].pos]),epl(mdf[tim].val);
	swap(a[mdf[tim].pos],mdf[tim].val);
}
int values;
signed main()
{
	read(n,q);
	rep(i,1,n)
	{
	    read(a[i]);
	    if(mp[a[i]]) a[i]=mp[a[i]];
	    else a[i]=mp[a[i]]=++values;
	}
	rep(i,1,q)
	{
		read(opt);
		if(opt==1)
		{
			++qcnt;
			read(qrs[qcnt].l,qrs[qcnt].r);
			qrs[qcnt].t=mcnt;
			qrs[qcnt].id=qcnt;
		}
		else
		{
			++mcnt;
			read(mdf[mcnt].pos,mdf[mcnt].val);
			if(mp[mdf[mcnt].val]) mdf[mcnt].val=mp[mdf[mcnt].val];
			else mdf[mcnt].val=mp[mdf[mcnt].val]=++values;
		}
	}
	static int siz=pow(n,2.0/3);
	sort(qrs+1,qrs+qcnt+1,[](queries a,queries b){return a.l/siz==b.l/siz?a.r==b.r?a.t<b.t:a.r<b.r:a.l<b.l;});
	int l=1,r=0,t=0;
	mex.set();
	mex[0]=0;	
	rep(i,1,qcnt)
	{
		while(r<qrs[i].r) epl(a[++r]);
		while(l>qrs[i].l) epl(a[--l]);
		while(r>qrs[i].r) ers(a[r--]);
		while(l<qrs[i].l) ers(a[l++]);
		while(t<qrs[i].t) cgt(i,++t);
		while(t>qrs[i].t) cgt(i,t--);
		ans[qrs[i].id]=mex._Find_first();
	}
	rep(i,1,qcnt) writeln(ans[i]);
	return 0;
}