#include <iostream>
#include <vector>
#include <algorithm>
#include<set>
#include <cinttypes>
#include <string>
#include <map>

using namespace std;

vector<int64_t> f(const vector<int64_t>& a) {
    vector<vector<int64_t> > b(a.size());
    for (int i = a.size()-1; i >= 0; i--) {
        b[a[i]-1].push_back(i);
    }
    set<pair<int64_t, int64_t> > s;
    for (int i = 0; i < b.size(); i++) {
        if (b[i].size() > 0) {
            s.insert({b[i].back(), i});
            b[i].pop_back();
        }
    }
    vector<int64_t> ans(a.size(), 0);
    for (int i = 1; i <= a.size(); i++) {
        auto el = (*s.begin());
        s.erase(s.begin());
        ans[el.first] = i;
        if (b[el.second].size() > 0) {
            s.insert({b[el.second].back(), el.second})'
            b[el.second].pop_back();
        }
    }
    return ans;
}

int main() {
    int64_t n, q;
    cin >> n >> q;
    vector<int64_t> a(n);
    for (auto& el : a) {
        cin >> el;
    }
    vector<int64_t> now = f(a);
    bool fl = true;
    while (q--) {
        int64_t t, x;
        cin >> t >> x;
        if (t == 1) {
            swap(a[x], a[x-1]);
            if (a[x] != a[x-1]) {
                fl = false;
            }
        } else {
            if (!fl) {
                now = f(a);
                fl = true;
            }
            cout << now[x-1] << '\n';
        }
    }
    return 0;
}
