#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <ctime>
#include <random>
#include <map>

#define f first
#define s second
#define pb push_back
using namespace std;

template<typename T1, typename T2> inline void chkmin(T1 & x, T2 y) {if (x > y) x = y;}
template<typename T1, typename T2> inline void chkmax(T1 & x, T2 y) {if (x < y) x = y;}

typedef long long ll;

const int MAXN = 1e5 + 1, MAXC = 2e5 + 1, BLOCK = 300;
pair<int, pair<int, int>> chng[MAXN];
int cnt[MAXC], cntofcnt[MAXN], ans[MAXN], a[MAXN];

struct req {
    int t, l, r, num;
    req(int _t, int _l, int _r, int _num) {
        t = _t, l = _l, r = _r, num = _num;
    }
};

bool cmp(req & a, req & b) {
    int bla = a.t / BLOCK, blb = b.t / BLOCK;
    if (bla != blb) return bla < blb;
    bla = a.l / BLOCK, blb = b.l / BLOCK;
    if (bla != blb) return bla < blb;
    return a.r < b.r;
}

void add_el(int x) {
    --cntofcnt[cnt[x]];
    ++cntofcnt[++cnt[x]];
}

void del_el(int x) {
    --cntofcnt[cnt[x]];
    ++cntofcnt[--cnt[x]];
}

int get_coor(vector<int> & vals, int x) {
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}

void change(int l, int r, int pos, int nv) {
    if (l <= pos && pos <= r)
        del_el(a[pos]), add_el(nv);
    a[pos] = nv;
}

int get_ans() {
    for (int i = 1; ; ++i)
        if (!cntofcnt[i]) return i;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("input.txt", "r", stdin);
    int n, q;
    cin >> n >> q;
    int changes = 0;
    vector<int> vals;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        vals.pb(a[i]);
    }
    vector<req> reqs;

    for (int i = 0; i < q; ++i) {
        int t, l, r;
        cin >> t >> l >> r;
        ans[i] = -1;
        if (t == 1)
            reqs.pb(req(changes, l, r, i));
        else {
            chng[changes++] = {l, {a[l], r}};
            vals.pb(r);
            a[l] = r;
        }
    }
    for (int i = changes - 1; i >= 0; --i)
        a[chng[i].f] = chng[i].s.f;
    sort(vals.begin(), vals.end());
    int n1 = unique(vals.begin(), vals.end()) - vals.begin();
    while (vals.size() > n1)
        vals.pop_back();

    for (int i = 1; i <= n; ++i) {
        a[i] = get_coor(vals, a[i]);
    }
    for (int i = 0; i < changes; ++i) {
        chng[i].s = {get_coor(vals, chng[i].s.f), get_coor(vals, chng[i].s.s)};
    }
    sort(reqs.begin(), reqs.end(), cmp);
    int l = 1, r = 0, ct = 0;
    for (auto i : reqs) {

        while (r < i.r)
            add_el(a[++r]);
        while (r > i.r)
            del_el(a[r--]);
        while (l < i.l)
            del_el(a[l++]);
        while (l > i.l)
            add_el(a[--l]);
        while (ct < i.t) {
            change(l, r, chng[ct].f, chng[ct].s.s);
            ++ct;
        }
        while (ct > i.t) {
            --ct;
            change(l, r, chng[ct].f, chng[ct].s.f);
        }
        ans[i.num] = get_ans();
    }
    for (int i = 0; i < q; ++i) {
        if (ans[i] != -1)
            cout << ans[i] << '\n';
    }
    return 0;
}