#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
    }
    int c = *max_element(a.begin(), a.end()) + 1;
    vector<int> whn;
    for (int t = 0; t < q; ++t) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int x;
            cin >> x;
            x--;
            swap(a[x], a[x + 1]);
            whn.clear();
        } else {
            if (whn.empty()) {
                whn.resize(n);
                priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> qq;
                vector<vector<int>> col(c);
                for (int i = n - 1; i >= 0; --i) {
                    col[a[i]].push_back(i);
                }
                for (int i = 0; i < c; ++i) {
                    if (!col[i].empty()) {
                        qq.emplace(col[i].back(), i);
                    }
                }
                int prv = -1;
                for (int z = 0; z < n; ++z) {
                    auto [i, cl] = qq.top();
                    qq.pop();
                    if (qq.empty() || cl != prv) {
                        whn[i] = z;
                        col[cl].pop_back();
                        if (!col[cl].empty()) {
                            qq.emplace(col[cl].back(), cl);
                        }
                        prv = cl;
                    } else {
                        auto [i2, cl2] = qq.top();
                        qq.pop();
                        whn[i2] = z;
                        col[cl2].pop_back();
                        qq.emplace(i, cl);
                        if (!col[cl2].empty()) {
                            qq.emplace(col[cl2].back(), cl2);
                        }
                        prv = cl2;
                    }
                }
            }
            int x;
            cin >> x;
            cout << whn[x - 1] + 1 << "\n";
        }
    }
}