#include <bits/stdc++.h>
using namespace std;
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*10+ch-48;ch=getchar();}
    return x*f;
}
const int N = 5e6;
int n, m, sq, res, Cnum, Qnum, a[N], cnt[N], st[N], ans[N];
struct Change
{
    int pos, val;
} C[N];
struct Query
{
    int l, r, id, pre;
    bool operator<(const Query &o) const
    {
        if (l / sq != o.l / sq)
            return l < o.l;
        if (l / sq & 1)
            return r < o.r;
        return r > o.r;
    }
} Q[N];
inline void add(int pos)
{
    --st[cnt[pos]];
    ++st[++cnt[pos]];
}
inline void del(int pos)
{
    --st[cnt[pos]];
    ++st[--cnt[pos]];
}
inline void swap(int &a, int &b) { a ^= b, b ^= a, a ^= b; }
inline void update(int now, int i)
{
    if (C[now].pos >= Q[i].l and C[now].pos <= Q[i].r)
        del(a[C[now].pos]), add(C[now].val);
    swap(C[now].val, a[C[now].pos]);
}
vector<int> b;
signed main()
{
    n = read(), m = read();
    sq = pow(n, 3.0 / 4.0);
    for (int i = 1; i <= n; i++)
        a[i] = read(), b.emplace_back(a[i]);
    for (int i = 1; i <= m; i++)
    {
        int op = read();
        if (op == 1)
        {
            Q[++Qnum].l = read();
            Q[Qnum].r = read();
            Q[Qnum].pre = Cnum;
            Q[Qnum].id = Qnum;
        }
        else
        {
            C[++Cnum].pos = read();
            C[Cnum].val = read();
            b.emplace_back(C[Cnum].val);
        }
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    for (int i = 1; i <= Cnum; i++)
        C[i].val = lower_bound(b.begin(), b.end(), C[i].val) - b.begin();
    sort(Q + 1, Q + Qnum + 1);
    int l = 1, r = 0, now = 0;
    for (int i = 1; i <= Qnum; i++)
    {
        while (r < Q[i].r) add(a[++r]);
        while (l > Q[i].l) add(a[--l]);
        while (r > Q[i].r) del(a[r--]);
        while (l < Q[i].l) del(a[l++]);
        while (now < Q[i].pre) update(++now, i);
        while (now > Q[i].pre) update(now--, i);
        for (ans[Q[i].id] = 1; st[ans[Q[i].id]]; ans[Q[i].id]++)
            ;
    }
    for (int i = 1; i <= Qnum; i++)
        cout << ans[i] << endl;
    return 0;
}