#include "bits/stdc++.h"

#pragma GCC optimize("03,unroll-loops")

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define len(x) ((int)x.size())

using namespace std;
using ll = long long;
using ld = long double;

const int inf = 1e9;

void solve() {
    int n, tt;
    cin >> n >> tt;
    vector<int> a(n);
    for (auto &h : a) {
        cin >> h;
        --h;
    }
    vector<int> mp(n);
    vector<set<int>> ind(n);
    set<int> se;
    se.insert(inf);
    for (int i = 0; i < n; ++i) {
        ind[a[i]].insert(i);
    }
    for (auto &v : ind) {
        if (len(v)) {
            se.insert(*v.begin());
        }
    }
    mp[0] = 1;
    int ls = 2, now = 0;
    while (ls <= n) {
        ind[a[now]].erase(ind[a[now]].begin());
        se.erase(now);
        if (*se.begin() == inf) {
            while (len(ind[a[now]])) {
                mp[*ind[a[now]].begin()] = ls++;
                ind[a[now]].erase(ind[a[now]].begin());
            }
            break;
        }
        auto q = *se.begin();
        mp[q] = ls++;
        if (len(ind[a[now]])) {
            se.insert(*ind[a[now]].begin());
        }
        now = q;
    }

    while (tt--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int x;
            cin >> x;
            --x;
            if (a[x] != a[x + 1]) {
                swap(a[x], a[x + 1]);
                for (auto &v : ind) v.clear();
                se.clear();
                se.insert(inf);
                for (int i = 0; i < n; ++i) {
                    ind[a[i]].insert(i);
                }
                for (auto &v : ind) {
                    if (len(v)) {
                        se.insert(*v.begin());
                    }
                }

                ls = 2, now = 0;
                while (ls <= n) {
                    ind[a[now]].erase(ind[a[now]].begin());
                    se.erase(now);
                    if (*se.begin() == inf) {
                        while (len(ind[a[now]])) {
                            mp[*ind[a[now]].begin()] = ls++;
                            ind[a[now]].erase(ind[a[now]].begin());
                        }
                        break;
                    }
                    auto q = *se.begin();
                    mp[q] = ls++;
                    if (len(ind[a[now]])) {
                        se.insert(*ind[a[now]].begin());
                    }
                    now = q;
                }
            }
        } else {
            int y;
            cin >> y;
            --y;
            cout << mp[y] << '\n';
        }
    }
}

/*
10 10
3 1 1 2 2 1 1 2 2 2
2 2
2 3
2 4
2 10
1 1
2 2
2 3
2 4
2 5
2 10


10 10
1 2 2 2 3 4 5 6 7 8
2 1
1 1
2 2
1 2
2 3
1 3
2 4
1 4
2 3
2 5

*/

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
        cout << '\n';
    }
}
