#include <bits/stdc++.h>

using namespace std;

#define less albert
#define great liza

const int N = 1e5 + 150;
int L;

int n, q;
int a[N], cnt[N], ans[N], val[N];
int kek[N];
set <int> have;

int get_ans()
{
    return *have.begin();
}

void rem(int v)
{
    if (v == 0) return;
    kek[v]--;
    if (kek[v] == 0)
    {
        have.insert(v);
    }
}

void add(int v)
{
    if (v == 0) return;
    kek[v]++;
    if (have.count(v))
    {
        have.erase(v);
    }
}

void great(int elem)
{
    rem(cnt[elem]);
    cnt[elem]++;
    add(cnt[elem]);
}

void less(int elem)
{
    rem(cnt[elem]);
    cnt[elem]--;
    add(cnt[elem]);
}

struct query
{
    int l, r, tx, num;
    query(int _l, int _r, int _tx, int i)
    {
        l = _l;
        r = _r;
        tx = _tx;
        num = i;
    }
};

struct change
{
    int pos, value, undo;
    change(int a, int b)
    {
        pos = a;
        value = b;
    }
};

bool cmp(query &a, query &b)
{
    int v1 = a.tx / L, v2 = b.tx / L;
    if (v1 != v2) return v1 < v2;
    v1 = a.l / L, v2 = b.l / L;
    if (v1 != v2) return v1 < v2;
    return a.r < b.r;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n + 1; ++i) have.insert(i);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    int was = 0;
    vector <query> s;
    vector <change> c;
    int has = 0;
    for (int i = 0; i < q; ++i)
    {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1)
        {
            --l, --r;
            s.push_back(query(l, r, has, i));
        }
        else
        {
            has++;
            --l;
            c.push_back(change(l, r));
        }
    }
    L = pow((long long)(n * n), 1.0 / 3.0);
    sort(s.begin(), s.end(), cmp);

    for (int i = 0; i < n; ++i) val[i] = a[i];
    for (auto &i : c)
    {
        i.undo = val[i.pos];
        val[i.pos] = i.value;
    }

    int l = s[0].l;
    int r = s[0].r;
    int curT = s[0].tx - 1;

    for (int i = l; i <= r; ++i)
    {
        great(a[i]);
    }

    for (int i = 0; i <= curT; ++i)
    {
        int ps = c[i].pos;
        int vl = c[i].value;
        less(a[ps]);
        great(vl);
        a[ps] = vl;
    }

    ans[s[0].num] = get_ans();

    for (int i = 1; i < s.size(); ++i)
    {
        int curL = s[i].l;
        int curR = s[i].r;
        int T = s[i].tx - 1;
        while (r < curR)
        {
            great(a[++r]);
        }
        while (r > curR)
        {
            less(a[r--]);
        }
        while (l < curL)
        {
            less(a[l++]);
        }
        while (l > curL)
        {
            great(a[--l]);
        }

        while (curT < T)
        {
            curT++;
            int ps = c[curT].pos;
            int vl = c[curT].value;
            if (l <= ps && ps <= r)
            {
                less(a[ps]);
                great(vl);
            }
            a[ps] = vl;
        }

        while (curT > T)
        {
            int ps = c[curT].pos;
            int vl = c[curT].value;
            int un = c[curT].undo;
            if (l <= ps && ps <= r)
            {
                less(a[ps]);
                great(un);
            }
            a[ps] = un;
            curT--;
        }
        ans[s[i].num] = get_ans();

    }

    for (int i = 0; i < q; ++i)
    {
        if (ans[i] == 0) continue;
        cout << ans[i] << "\n";
    }

    return 0;
}

/*
* int overflow, array bounds
* special cases (n=1?), set tle
* do smth instead of nothing and stay organized
* double troubles
* same points in geoma
* in game theory find win cases
*/