// clang-format off
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define all(a) a.begin(), a.end()
#define int long long
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long double ld;

const int c = 2200;

struct Query {
    int l, r, t;
    Query(int _l, int _r, int _t) : l(_l), r(_r), t(_t) {}

    bool operator<(const Query& other) {
        if (l / c == other.l / c) {
            if (r / c == other.r / c) {
                if ((l / c + r / c) & 1) {
                    return t > other.t;
                }
                return t < other.t;
            }
            if ((l / c) & 1) {
                return r > other.r;
            }
            return r < other.r;
        }
        return l < other.l;
    }
};

struct Condition {
    int ind = -1, last = -1, now = -1;
    bool upd = false;
    Condition(int _i, int _l, int _n, bool u) : ind(_i), last(_l), now(_n), upd(u) { }
};

struct Set_sq {
    const int sq_2 = 600, sq_4 = 50;
    int n;
    vector<int> cnt, mark_st, st, st_sq;
    Set_sq(int _n) : n(_n) {
        cnt.resize(n);
        mark_st.resize(sq_2, 0); mark_st[0] = 1;
        st.resize(sq_2, 0); st[0] = 1;
        st_sq.resize(sq_4, 0); st_sq[0] = 1;
    }
    void erase(int x) {
        if(cnt[x] && cnt[x] < sq_2) {
            mark_st[cnt[x]]--;
            if(!mark_st[cnt[x]]){
                st[cnt[x]] = 0;
                st_sq[cnt[x] / sq_4]--;
            }
        }
        cnt[x]--;
        if (cnt[x] && cnt[x] < sq_2) {
            mark_st[cnt[x]]++;
            if(mark_st[cnt[x]] == 1) {
                st[cnt[x]] = 1;
                st_sq[cnt[x] / sq_4]++;
            }
        }
    }
    void insert(int x) {
        if (cnt[x] && cnt[x] < sq_2) {
            mark_st[cnt[x]]--;
            if (!mark_st[cnt[x]]) {
                st[cnt[x]] = 0;
                st_sq[cnt[x] / sq_4]--;
            }
        }
        cnt[x]++;
        if (cnt[x] && cnt[x] < sq_2) {
            mark_st[cnt[x]]++;
            if (mark_st[cnt[x]] == 1) {
                st[cnt[x]] = 1;
                st_sq[cnt[x] / sq_4]++;
            }
        }
    }
    int get_fst() {
        int it = 0;
        while(st_sq[it] == sq_4) { it++; }
        int res = it * sq_4;
        while(st[res] == 1) { res++; }
        return res;
    }
};
signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n), init_sub, compress;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    compress = init_sub = a;
    vector<Condition> up; up.push_back(Condition(-1, -1, -1, false));
    vector<Query> mo;

    for (int i = 0; i < q; i++) {
        int type; cin >> type;
        if (type == 1) {
            int l, r; cin >> l >> r;
            l--, r--;
            mo.push_back(Query(l, r, i + 1));
            up.push_back(Condition(-1, -1, -1, false));
        }
        if (type == 2) {
            int p, x; cin >> p >> x;
            p--;
            up.push_back(Condition(p, init_sub[p], x, true));
            init_sub[p] = x;
            compress.push_back(x);
        }
    }


    {
        sort(all(compress)); compress.resize(unique(all(compress)) - compress.begin());
        for (int i = 0; i < n; i++) {
            a[i] = lower_bound(all(compress), a[i]) - compress.begin();
        }
        for (int i = 0; i < (int)up.size(); i++) {
            if (!up[i].upd) { continue; }
            up[i].last = lower_bound(all(compress), up[i].last) - compress.begin();
            up[i].now = lower_bound(all(compress), up[i].now) - compress.begin();
        }
    }

    init_sub.clear();
    Set_sq U((int)compress.size() + 1);
    sort(all(mo));

    auto add = [&](int x) {
        U.insert(x);
    };
    auto del = [&](int x) {
        U.erase(x);
    };

    vector<int> ans(q, -1);
    int l = 0, r = -1, time = -1;
    for (const Query& i : mo) {
        while (time < i.t) {
            Condition& recalc = up[++time];
            if (recalc.upd) {
                if(recalc.ind >= l && recalc.ind <= r){
                    del(recalc.last);
                    add(recalc.now);
                }
                a[recalc.ind] = recalc.now;
            }
        }
        while (time > i.t) {
            Condition& recalc = up[time--];
            if (recalc.upd) {
                if (recalc.ind >= l && recalc.ind <= r) {
                    del(recalc.now);
                    add(recalc.last);
                }
                a[recalc.ind] = recalc.last;
            }
        }

        while (l > i.l) {
            add(a[--l]);
        }
        while (r < i.r) {
            add(a[++r]);
        }
        while (l < i.l) {
            del(a[l++]);
        }
        while (r > i.r) {
            del(a[r--]);
        }

        ans[i.t - 1] = U.get_fst();
    }

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