#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,t;
int a[N],b[N],kc[N],xf;
int op[N],lq[N],rq[N];
struct query{int l,r,t,id;}q[N];
int ux[N],uy[N],ry[N];
int cnt[N],tot[N],ans[N];
bool cmp(query q1,query q2)
{
    if(q1.l/t!=q2.l/t)
        return q1.l/t<q2.l/t;
    if(q1.r/t!=q2.r/t)
        return q1.r/t<q2.r/t;
    return q1.t<q2.t;
}
void add(int x)
{
    --tot[cnt[x]];
    ++cnt[x];
    ++tot[cnt[x]];
}
void del(int x)
{
    --tot[cnt[x]];
    --cnt[x];
    ++tot[cnt[x]];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    t=pow(n,0.6666);
    for(int i=1;i<=n;++i)
        cin>>a[i],kc[++xf]=a[i];
    for(int i=1;i<=m;++i)
    {
        cin>>op[i]>>lq[i]>>rq[i];
        if(op[i]==2)
            kc[++xf]=rq[i];
    }
    sort(kc+1,kc+xf+1);
    xf=unique(kc+1,kc+xf+1)-kc-1;
    for(int i=1;i<=n;++i)
        a[i]=b[i]=lower_bound(kc+1,kc+xf+1,a[i])-kc;
    for(int i=1;i<=m;++i)
        if(op[i]==2)
            rq[i]=lower_bound(kc+1,kc+xf+1,rq[i])-kc;
    int tq=0,tc=0,ver=0;
    for(int i=1;i<=m;++i)
    {
        if(op[i]==1)
        {
            ++tq;
            q[tq].l=lq[i];
            q[tq].r=rq[i];
            q[tq].t=ver;
            q[tq].id=tq;
        }
        else
        {
            ++tc;++ver;
            ux[tc]=lq[i];
            uy[tc]=rq[i];
            ry[tc]=b[ux[i]];
            b[ux[i]]=uy[i];
        }
    }
    sort(q+1,q+tq+1,cmp);
    for(int i=1,l=1,r=0,t=0;i<=tq;++i)
    {
        while(l>q[i].l)
            add(a[--l]);
        while(r<q[i].r)
            add(a[++r]);
        while(l<q[i].l)
            del(a[l++]);
        while(r>q[i].r) 
            del(a[r--]);
        while(t<q[i].t)
        {
            ++t;
            if(q[i].l<=ux[t]&&ux[t]<=q[i].r)
            {
                del(a[ux[t]]);
                a[ux[t]]=uy[t];
                add(a[ux[t]]);
            }
            a[ux[t]]=uy[t];
        }
        while(t>q[i].t)
        {
            if(q[i].l<=ux[t]&&ux[t]<=q[i].r)
            {
                del(a[ux[t]]);
                a[ux[t]]=ry[t];
                add(a[ux[t]]);
            }
            a[ux[t]]=ry[t];
            --t;
        }
        for(ans[q[i].id]=1;tot[ans[q[i].id]];++ans[q[i].id]);
    }
    for(int i=1;i<=tq;++i)
        cout<<ans[i]<<'\n';
}