#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int inf = 0x3f3f3f3f;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 67
#endif

struct segtree {
    vector<pii> tree;
    int size;
    void init(int n) {
        size = 1;
        while (size < n)size *= 2;
        tree.assign(2 * size - 1, {inf, inf});
    }
    void set(int ind, int val) {
        set(ind, val, 0, 0, size);
    }
    void set(int ind, int val, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = {val, lx};
            return;
        }
        int mid = (lx + rx) / 2;
        if (ind < mid) {
            set(ind, val, 2 * x + 1, lx, mid);
        } else {
            set(ind, val, 2 * x + 2, mid, rx);
        }
        tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    }
    pii get(int l, int r) {
        return get(l, r, 0, 0, size);
    }
    pii get(int l, int r, int x, int lx, int rx) {
        if (rx <= l || r <= lx)return {inf, inf};
        if (lx >= l && rx <= r) {
            return tree[x];
        }
        int mid = (lx + rx) / 2;
        auto g1 = get(l, r, 2 * x + 1, lx, mid);
        auto g2 = get(l, r, 2 * x + 2, mid, rx);
        return min(g1, g2);
    }
};

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int &i : a)cin >> i;
    vector<vector<int>> pos(n + 1);
    for (int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        pos[i].push_back(inf);
    }
    vector<int> uk(n + 1);
    vector<int> ans(n);
    segtree sg;
    auto get = [&]() {
        sg.init(n + 1);
        for (int i = 1; i <= n; ++i) {
            uk[i] = 0;
            sg.set(i, pos[i][0]);
        }
        auto [i, val] = sg.get(1,n + 1);
        int ind = 0;
        while (i < inf) {
            ans[i] = ind++;
            uk[val]++;
            sg.set(val, pos[val][uk[val]]);
            pii g1 = sg.get(1, val);
            g1 = min(g1, sg.get(val + 1, n + 1));
            i = g1.first;
            if (i == inf)break;
            val = g1.second;
        }
        while (uk[val] < (int)pos[val].size() - 1) {
            ans[pos[val][uk[val]]] = ind++;
            uk[val]++;
        }
    };
    auto upd =[&](int i) {
        if (a[i] == a[i + 1])return;
        int j1 = lower_bound(all(pos[a[i]]), i) - pos[a[i]].begin();
        pos[a[i]][j1]++;
        int j2 = lower_bound(all(pos[a[i + 1]]), i) - pos[a[i + 1]].begin();
        pos[a[i + 1]][j2]--;
        swap(a[i], a[i + 1]);
    };
    bool flag = 1;
    get();
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int x; cin >> x;
            x--;
            upd(x);
            flag = 0;
        } else {
            int y; cin >> y;
            if (!flag) {
                get();
                flag = 1;
            }
            y--;
            cout << ans[y] + 1 << '\n';
        }
    }
}

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    int tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
        if (tt) {
            cout << '\n';
        }
    }
}