#include <bits/stdc++.h>

//#define int long long
using namespace std;
using ll = long long;
const int T = 5e5 + 10;

vector<int> col[T];
int sz[T];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n, 0);
    vector<int> gd(n, 0);
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        int aa;
        cin >> aa;
        col[aa].push_back(i);
        a[i] = aa;
        gd[i] = (int)col[aa].size() - 1;
        mx = max(mx, aa);
    }
    vector<int> och(n, 0);
    set<pair<int, int>> st;
    for (int i = 1; i <= n; ++i) {
        if (!col[i].empty() && col[i][0] != 0) {
            st.insert({col[i][0], i});
        }
    }

    int pred = a[0];
    if ((int) col[a[0]].size() == 1) pred = -1;
    vector<int> her(n, 0);
    sz[a[0]] = 1;
    for (int i = 1; i < n; ++i) {
        auto [it, c] = *st.begin();
        st.erase({it, c});
        int numb = sz[c];
        ++sz[c];
        och[i] = it;
        her[it] = i;
        if (pred != -1) {
            st.insert({col[pred][sz[pred]], pred});
            pred = -1;
        }
        if (st.empty()) {
            if (i < n - 1) st.insert({col[c][sz[c]], c});
        } else {
            if (numb + 1 < (int)col[c].size()) pred = c;
        }
    }
    if (mx == 2) {
        for (int z = 0;z < q; ++z) {
            int t;
            cin >> t;
            if (t == 1) {
                int x;
                cin >> x;
                --x;

            } else {
                int y;
                cin >> y;
                --y;
                cout << her[y] + 1 << "\n";
            }
        }
        return 0;
    }
    for (int z = 0; z < q; ++z) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            --x;

            st.clear();
            int cl1 = a[x];
            int cl2 = a[x + 1];
            if (cl1 == cl2) continue;
            col[cl1][gd[x]] = x + 1;
            col[cl2][gd[x + 1]] = x;
            a[x] = cl2;
            a[x + 1] = cl1;
            int zzz = gd[x];
            gd[x] = gd[x + 1];
            gd[x + 1] = zzz;

            for (int i = 1; i <= n; ++i) {
                if (!col[i].empty() && i != a[0]) {
                    st.insert({col[i][0], i});
                }
                sz[i] = 0;
            }
            pred = a[0];
            if ((int) col[a[0]].size() == 1) pred = -1;
            sz[a[0]] = 1;
            for (int i = 1; i < n; ++i) {
                auto [it, c] = *st.begin();
                st.erase({it, c});
                int numb = sz[c];
                ++sz[c];
                och[i] = it;
                her[it] = i;
                if (pred != -1) {
                    st.insert({col[pred][sz[pred]], pred});
                    pred = -1;
                }
                if (st.empty()) {
                    if (i < n - 1) st.insert({col[c][sz[c]], c});
                } else {
                    if (numb + 1 < (int)col[c].size()) pred = c;
                }
            }
        } else {
            int y;
            cin >> y;
            --y;
            cout << her[y] + 1 << "\n";
        }
    }
    return 0;
}