#include <bits/stdc++.h>

using namespace std;

vector<int> calcans(vector<int> a) {
    int n = a.size();
    vector<set<int>> pos(n+1);    
    for(int i = 0; i < n; ++i) {
        pos[a[i]].emplace(i);
    }
    set<pair<int,int>> x;
    for(int i = 0; i <= n; ++i) {
        if(pos[i].size()) {
            x.emplace(*pos[i].begin(), i);
        }
    }
    vector<int> ans;
    vector<int> used(n);
    vector<int> pipisa(n);
    int cur= 1;
    int last = -1;
    for(int i = 0; i < n; ++i) {
        if(used[i]) {
            continue;
        }
        if(a[i] == -1) {
            pair<int,int> x1 = *x.begin();
            x.erase(x1);
            if(x1.second == a[i] && x.size()) {
                pair<int,int> y1 = *x.begin();
                x.erase(y1);
                pipisa[y1.first] = cur++;
                ans.emplace_back(y1.first);
                pos[y1.second].erase(pos[y1.second].begin());
                used[y1.first] = 1;
                if(pos[y1.second].size()) {
                    y1.first = *pos[y1.second].begin();
                    x.insert(y1);
                }
                x.insert(x1);
            } else if(x1.first != i) {
                pipisa[x1.first] = cur++;
                pos[x1.second].erase(pos[x1.second].begin());
                used[x1.first] = 1;
                if(pos[x1.second].size()) {
                    x1.first = *pos[x1.second].begin();
                    x.insert(x1);
                }                
            }
        }
        pipisa[i] = cur++;
        last = a[i];
        pair<int,int> x1 = {i, a[i]};
        x.erase(x1);     
        pos[x1.second].erase(pos[x1.second].begin());
        if(pos[x1.second].size()) {
            x1.first = *pos[x1.second].begin();
            x.insert(x1);
        }       

    }
    return pipisa;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n,q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i= 0; i < n; ++i) {
        cin >> a[i];        
    }
    vector<int> ans = calcans(a);
    for(int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if(t == 1) {
            int x;
            cin >> x;
            swap(a[x], a[x-1]);
            if(a[x] != a[x-1]) {                
                ans = calcans(a);
            }
        } else {
            int y;
            cin >> y;
            y--;
            cout << ans[y] << '\n';
        }
    }
    return 0;
}