#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int id;
            cin >> id;
            swap(arr[id - 1], arr[id]);
        } else {
            vector<vector<int>> ind(n + 1);
            set<pair<int, int>> st;
            for (int i = n - 1; i >= 0; i--) {
                ind[arr[i]].push_back(i);
            }
            for (int i = 0; i < n + 1; i++) {
                if (!ind[i].empty()) {
                    st.insert({ind[i].back(), i});
                }
            }
            vector<int> vec;
            int last = -1;
            while (!st.empty()) {
                auto it = st.begin();
                if (st.size() > 1 && st.begin()->second == last) {
                    ++it;
                }
                vec.push_back(it->first);
                last = it->second;
                ind[it->second].pop_back();
                if (!ind[it->second].empty()) {
                    st.insert({ind[it->second].back(), it->second});
                }
                st.erase(it);
            }
            int id;
            cin >> id;
            int res = 0;
            while (vec[res] != id - 1) {
                res++;
            }
            cout << res + 1 << '\n';
        }
    }
    return 0;
}