rt,orz

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Node{int l,r;};
int n,q,ans[100005],data[100005];
vector<int> ordinate;
int M,len,id[100005],cnt[200005],heap[100005];
Node node[200];
struct Qestion
{
	int l,r,id1,id2;
	bool operator <(const Qestion &target)const
		{return (id[l]^id[target.l])?(id[l]<id[target.l]):((id[l]&1)?(r<target.r):(r>target.r));}
};
struct Modify{int pos,value;};
int cnt1; Qestion qestion[100005];
int cnt2; Modify modify[100005];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void init()
{
	len=pow(n,(double)2.0/(double)3.0),M=ceil(n/len);
	for(int i=1;i<=M;++i) node[i].l=n/len*(i-1)+1,node[i].r=n/len*i; node[M].r=n;
	for(int i=1;i<=M;++i)
		for(int j=node[i].l;j<=node[i].r;++j) id[j]=i;
}
inline void update(const int pos) {heap[cnt[pos]]--,cnt[pos]++,heap[cnt[pos]]++;}
inline void revoke(const int pos) {heap[cnt[pos]]--,cnt[pos]--,heap[cnt[pos]]++;}
inline void change(const int id,const int index)
{
	if(qestion[id].l<=modify[index].pos&&modify[index].pos<=qestion[id].r) revoke(data[modify[index].pos]),update(modify[index].value);
	swap(data[modify[index].pos],modify[index].value);
}
inline void work()
{
	int L=1,R=0,index=0;
	for(int i=1;i<=cnt1;++i)
	{
		while(L<qestion[i].l) revoke(data[L++]);
		while(L>qestion[i].l) update(data[--L]);
		while(R<qestion[i].r) update(data[++R]);
		while(R>qestion[i].r) revoke(data[R--]);
		while(index<qestion[i].id2) change(i,++index);
		while(index>qestion[i].id2) change(i,index--);
		for(ans[qestion[i].id1]=1;heap[ans[qestion[i].id1]];ans[qestion[i].id1]++);
	}
}
int main()
{
	n=read(),q=read(),init();
	for(int i=1;i<=n;++i) data[i]=read(),ordinate.push_back(data[i]);
	for(int i=1;i<=q;++i)
	{
		int opt=read(),l=read(),r=read();
		if(opt==1) cnt1++,qestion[cnt1]=(Qestion){l,r,cnt1,cnt2};
		if(opt==2) cnt2++,modify[cnt2]=(Modify){l,r},ordinate.push_back(r);
	}
	sort(ordinate.begin(),ordinate.end()),ordinate.erase(unique(ordinate.begin(),ordinate.end()),ordinate.end());
	for(int i=1;i<=n;++i) data[i]=lower_bound(ordinate.begin(),ordinate.end(),data[i])-ordinate.begin()+1;
	for(int i=1;i<=cnt2;++i) modify[i].value=lower_bound(ordinate.begin(),ordinate.end(),modify[i].value)-ordinate.begin()+1;
	sort(qestion+1,qestion+cnt1+1),work();
	for(int i=1;i<=cnt1;++i) printf("%d\n",ans[i]);
	return 0;
}