//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;
// gp_hash_table<int, int>table;
typedef tree<
    ll,
    null_type,
    less<ll>,
    rb_tree_tag,
    tree_order_statistics_node_update>
ordered_set;
//find_by_order(x) - итератор на k по величине элемент
//order_of_key(x) - колво элементов в множестве строго меньших чем наш элемент
vector<vector<ll> > graph;

struct segment_tree {
    segment_tree() {
    }

    segment_tree(ll lb, ll rb) : lb(lb), rb(rb), pos(lb) {
        if (lb != rb) {
            ll mid = (lb + rb) / 2;
            l = new segment_tree(lb, mid);
            r = new segment_tree(mid + 1, rb);
        }
    }

    void push() {
        if (l) {
            l->dd += dd;
        }
        if (r) {
            r->dd += dd;
        }
        if (dd) {
            mn += dd;
        }
    }

    void set(ll ps, ll x) {
        if (lb == rb) {
            mn = x;
            return;
        }
        ll mid = (lb + rb) / 2;
        if (ps <= mid) {
            l->set(ps, x);
        } else {
            r->set(ps, x);
        }
        if (l->mn <= r->mn) {
            mn = l->mn;
            pos = l->pos;
        } else {
            mn = r->mn;
            pos = r->pos;
        }
    }

    void add(ll lm, ll rm, ll x) {
        if (lb > rm || rb < lm) {
            return;
        }
        if (lb >= lm && rb <= rm) {
            dd += x;
            push();
            return;
        }
        l->add(lm, rm, x);
        r->add(lm, rm, x);
        if (l->mn <= r->mn) {
            mn = l->mn;
            pos = l->pos;
        } else {
            mn = r->mn;
            pos = r->pos;
        }
    }

    pair<ll,ll> get_min(ll lm, ll rm) {
        push();
        if (lb > rm || rb < lm) {
            return {1e9, -1};
        }
        if (lb >= lm && rb <= rm) {
            return {mn, pos};
        }
        return min(l->get_min(lm, rm), r->get_min(lm, rm));
    }

    ll dd = 0;
    ll mn = 1e9, pos = -1;
    ll lb, rb;
    segment_tree *l = nullptr, *r = nullptr;
};

const ll MOD = 998244353;
ll binpow(ll a, ll n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return a % MOD;
    }
    ll g = binpow(a, n / 2);
    if (n % 2 == 0) {
        return (g * g) % MOD;
    }
    return (((g * g) % MOD) * a) % MOD;
}


void solve() {
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n);
    vector<vector<ll> > colors(n + 1), copy;
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
        colors[a[i]].push_back(i);
    }
    copy = colors;
    for (auto &i: colors) {
        reverse(i.begin(), i.end());
    }
    vector<ll> ans(n);
    segment_tree seg(0, n);
    for (ll i = 0; i <= n; ++i) {
        if (colors[i].empty()) continue;
        seg.set(i, colors[i].back());
    }
    ll cnt = n - 1;
    ans[0] = 1;
    ll color = a[0];
    colors[a[0]].pop_back();
    if (colors[a[0]].empty()) {
        seg.set(a[0], 1e9);
    } else {
        seg.set(a[0], colors[a[0]].back());
    }
    ll ps = 2;
    while (cnt > 0) {
        pair<ll,ll> f = min(seg.get_min(0, color - 1), seg.get_min(color + 1, n));
        if (f.second == -1) {
            while (!colors[color].empty()) {
                ll back = colors[color].back();
                ans[back] = ps++;
                colors[color].pop_back();
            }
            cnt = 0;
        } else {
            ll pp = f.second;
            ans[colors[pp].back()] = ps++;
            colors[pp].pop_back();
            if (colors[pp].empty()) {
                seg.set(pp, 1e9);
            } else {
                seg.set(pp, colors[pp].back());
            }
        }
        color = f.second;
    }
    colors = copy;
    vector<vector<ll> > ansColors(n + 1);
    vector<ll> pos(n);
    for (ll i = 0; i <= n; ++i) {
        for (ll j = 0; j < colors[i].size(); ++j) {
            pos[colors[i][j]] = j;
            ansColors[i].push_back(ans[colors[i][j]]);
        }
    }
    vector<segment_tree> segs(n + 1);
    for (ll i = 0; i <= n; ++i) {
        segs[i] = segment_tree(0, colors[i].size());
        for (ll j = 0; j < ansColors[i].size(); ++j) {
            segs[i].set(j, ansColors[i][j]);
        }
    }
    while (q--) {
        ll type;
        cin >> type;
        if (type == 1) {
            ll x;
            cin >> x;
            --x;
            ll clr = a[x + 1];
            ll pps = pos[x + 1];
            segs[clr].add(pps, colors[clr].size() - 1, -1);
            clr = a[x];
            pps = pos[x];
            segs[clr].add(pps, colors[clr].size() - 1, 1);
        } else {
            ll y;
            cin >> y;
            --y;
            ll clr = a[y];
            ll pps = pos[y];
            cout << segs[clr].get_min(pps, pps).first << ' ';
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
#ifndef LOCAL
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
#endif
    ll t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
