#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
#ifdef LOCAL
    freopen("test", "r", stdin);
    freopen("res", "w", stdout);
#endif

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (auto &x : a) {
        cin >> x;
        x--;
    }

    vector<int> p(n), pos(n);

    vector<vector<int>> poses(n);
    for (int i = 0; i < n; ++i) {
        poses[a[i]].push_back(i);
    }

    vector<int> ind(n);
    set<pair<int, int>> st;
    for (int i = 0; i < n; ++i) {
        if (!poses[i].empty()) {
            st.emplace(poses[i][0], i);
        }
    }

    int last = -1;
    for (int i = 0; i < n; ++i) {
        if (st.begin()->second != last || st.size() == 1) {
            pos[i] = st.begin()->first;
            p[pos[i]] = i;
            int c = st.begin()->second;
            last = c;
            st.erase(st.begin());
            ind[c]++;
            if (ind[c] < poses[c].size()) {
                st.emplace(poses[c][ind[c]], c);
            }
        } else {
            auto b = st.begin();
            ++b;
            pos[i] = b->first;
            p[pos[i]] = i;
            int c = b->second;
            last = c;
            st.erase(b);
            ind[c]++;
            if (ind[c] < poses[c].size()) {
                st.emplace(poses[c][ind[c]], c);
            }
        }
    }

    while (q--) {
        int c;
        cin >> c;
        if (c == 1) {
            int x;
            cin >> x;
            x--;

            int d = p[x], e = p[x + 1];
            if (d > e) swap(d, e);
            if (d == 0 || a[pos[d - 1]] != a[pos[e]]) {
                swap(p[x], p[x + 1]);
                swap(pos[d], pos[e]);
            }
        } else {
            int y;
            cin >> y;
            y--;
            cout << p[y] + 1 << '\n';
        }
    }
}