3D MO

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <bitset>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <stack>
#include <queue>
#include <complex>


using namespace std;
using namespace __gnu_pbds;



/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")*/

/*
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,tune=native")
#pragma GCC target("avx2")
 #pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
 #pragma GCC optimization("O3")
*/

//#define int long long
#define ll long long
//#define int short int
#define eb emplace_back
#define pb push_back
#define ld long double
//#define ld double
#define mp make_pair
#define f first
#define s second
#define gleg(x) return cout << x, 0
#define pii pair <int, int>
#define deb(a) cerr << #a << " = " << a << '\n';
//#define sz(x) (int)s.size();
#define fast() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout << fixed << setprecision(9);     cerr << fixed << setprecision(12); }

template < typename firstType, typename secondType = null_type, class compare = less < firstType > >
struct sett {
    typedef tree <
            firstType,
            secondType,
            compare,
            rb_tree_tag,
            tree_order_statistics_node_update
    > _ ;
};


const int INF = 1e9 + 7;
const ld EPS = 1e-9;
const int MAXI = 350;
const int MOD = 998244353;
const int MOD1 = 1e9 + 7;
const int MAXST = 2000000;
const int P = 31;
const int P1 = 37;
const int N = 5100000;
const ld PI = 3.14159265358979323;
const int bp = 23;
//const int sz = 1 << bp;


ostream &operator<<(ostream &stream, const pair <int, int> &p) {
    stream << p.first << ' ' << p.second << ' ';
    return stream;
}

struct rq{
    int l, r, tm;

    rq(int _l, int _r, int _tm){
        l = _l;
        r = _r;
        tm = _tm;
    }

};

struct u {
    bool f;
    int pos, prx, x;

    u(){
        f = false;
    }

    u(int _pos, int _prx, int _x){
        f = true;
        pos  = _pos;
        prx = _prx;
        x = _x;
    }
};

int k;

bool cmp(rq &a, rq &b){
    if (a.l / k == b.l / k){
        if (a.r / k == b.r / k)
            return a.tm < b.tm;
        return ((a.r * (a.l / k % 2 == 1 ? -1 : 1)) < (b.r * (a.l / k % 2 == 1 ? -1 : 1)));
    }
    return a.l < b.l;
}

int cnt[310000], mx[310000];

void del(int x){
    if (cnt[x] == 1){
        mx[cnt[x]]--;
        cnt[x]--;
    }
    else{
        mx[cnt[x]]--;
        cnt[x]--;
        mx[cnt[x]]++;
    }
}

void add(int x){
    if (cnt[x] == 0){
        cnt[x]++;
        mx[cnt[x]]++;
    }
    else{
        mx[cnt[x]]--;
        cnt[x]++;
        mx[cnt[x]]++;
    }
}

signed main(){
    fast();
    srand(time(0));
    /*#ifdef _LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int n, m;
    cin >> n >> m;
    vector <int> a(n);
    unordered_map <int, int> p;

    for (int i = 0; i < n; i++){
        cin >> a[i];
        if (p.find(a[i]) == p.end())
            p[a[i]] = p.size();
        a[i] = p[a[i]];
    }
    vector <int> a1 = a;

    vector <rq> req;
    vector <u> upd(m + 10, u());
    for (int q = 0; q < m; q++){
        int c, l, r;
        cin >> c >> l >> r;

        if (c == 1){
            l--, r--;
            req.eb(rq(l, r, q));
        } else {
            l--;
            if (p.find(r) == p.end())
                p[r] = p.size();

            r = p[r];
            upd[q] = u(l, a1[l], r);
            a1[l] = r;
        }
    }

    k = 3500;

    sort(req.begin(), req.end(), cmp);

    int l = 0, r = -1, t = -1;

    vector <pair <int, int>> ans;
    //sqmex st = sqmex(n + m);


    for (int q = 0; q < (int)req.size(); q++){
        int l1 = req[q].l, r1 = req[q].r, tm = req[q].tm;

        while (r < r1){
            r++;
            add(a[r]);
        }

        while (l > l1){
            l--;
            add(a[l]);
        }

        while (r > r1){
            del(a[r]);
            r--;
        }

        while (l < l1){
            del(a[l]);
            l++;
        }

        while (t < tm) {
            t++;
            if (upd[t].f) {
                if (l <= upd[t].pos && r >= upd[t].pos) {
                    del(a[upd[t].pos]);
                    add(upd[t].x);
                }

                a[upd[t].pos] = upd[t].x;
            }
        }

        while (t > tm) {
            if (upd[t].f) {
                if (l <= upd[t].pos && r >= upd[t].pos){
                    del(a[upd[t].pos]);
                    add(upd[t].prx);
                }

                a[upd[t].pos] = upd[t].prx;
            }

            t--;
        }

        int cur;
        for (int i = 1; i < (int)3e5; i++){
            if (mx[i] == 0) {
                cur = i;
                break;
            }
        }
        ans.pb({req[q].tm, cur});
    }

    sort(ans.begin(), ans.end());

    for (auto i: ans)
        cout << i.s << '\n';

    return 0;
}