#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>>pos(n);
    vector<pair<int, int>>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = pos[a[i].first - 1].size();
        pos[a[i].first - 1].push_back(i);
    }
    int t, x;
    for (int i = 0; i < q; i++) {
        cin >> t >> x;
        x--;
        if (t == 1) {
            if (a[x].first == a[x + 1].first) {
                continue;
            }
            swap(a[x], a[x + 1]);
            pos[a[x].first - 1][a[x].second] = x;
            pos[a[x + 1].first - 1][a[x + 1].second] = x + 1;
        }
        else {
            set<pair<int, int>>s;
            vector<int>cnt(n, 1);
            for (int i = 0; i < n; i++) {
                if (pos[i].size()) {
                    s.insert({*pos[i].begin(), i});
                }
            }
            int c = 1;
            if ((*s.begin()).first == x) {
                cout << 1 << endl;
                continue;
            }
            int nc = (*s.begin()).second;
            s.erase(s.begin());
            if (cnt[nc] < pos[nc].size()) {
                s.insert({pos[nc][cnt[nc]], nc});
                cnt[nc]++;
            }
            while (true) {
                c++;
                if ((*s.begin()).second != nc || s.size() == 1) {
                    nc = (*s.begin()).second;
                    if ((*s.begin()).first == x) {
                        cout << c << endl;
                        break;
                    }
                    s.erase(s.begin());
                    if (cnt[nc] < pos[nc].size()) {
                        s.insert({pos[nc][cnt[nc]], nc});
                        cnt[nc]++;
                    }
                } else {
                    auto it = s.begin();
                    it++;
                    if ((*it).first == x) {
                        cout << c << endl;
                        break;
                    }
                    nc = (*it).second;
                    s.erase(it);
                    if (cnt[nc] < pos[nc].size()) {
                        s.insert({pos[nc][cnt[nc]], nc});
                        cnt[nc]++;
                    }
                }
            }
        }
    }
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    solve();
}