#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#define int long long
using ll = long long;
using namespace std;
// #pragma GCC optimize("O3, unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//  using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
//  tree_order_statistics_node_update>;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<vector<int>> pointers(n + 1);
    for (int i = 0; i < n; ++i) {
        pointers[a[i]].push_back(i);
    }
    vector<int> ans(n);
    bool f = 0;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            x--;
            auto lb = lower_bound(pointers[a[x]].begin(), pointers[a[x]].end(), x) - pointers[a[x]].begin();
            auto lb2 = lower_bound(pointers[a[x + 1]].begin(), pointers[a[x + 1]].end(), x + 1) - pointers[a[x + 1]].begin();
            pointers[a[x]][lb] = x + 1;
            pointers[a[x + 1]][lb2] = x;
            swap(a[x], a[x + 1]);
            f = 0;
        } else {
            int y;
            cin >> y;
            y--;
            if (!f) {
                priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
                vector<int> ptr(n + 1, 0);
                for (int i = 1; i <= n; ++i) {
                    if ((int)pointers[i].size() > ptr[i])
                        pq.push({pointers[i][ptr[i]], i});
                }
                int cur = -1;
                int it = 0;
                while (!pq.empty()) {
                    if (pq.size() == 1) {
                        auto v = pq.top();
                        pq.pop();
                        ans[v.first] = it;
                        ptr[v.second]++;
                        int i = v.second;
                        if ((int)pointers[i].size() > ptr[i])
                            pq.push({pointers[i][ptr[i]], i});
                        cur = i;
                    } else {
                        auto v = pq.top();
                        if (v.second != cur) {
                            pq.pop();
                            ans[v.first] = it;
                            ptr[v.second]++;
                            int i = v.second;
                            if ((int)pointers[i].size() > ptr[i])
                                pq.push({pointers[i][ptr[i]], i});
                            cur = i;
                        } else {
                            pq.pop();
                            auto d = pq.top();
                            pq.pop();
                            ans[d.first] = it;
                            ptr[d.second]++;
                            int i = d.second;
                            if ((int)pointers[i].size() > ptr[i])
                                pq.push({pointers[i][ptr[i]], i});
                            cur = i;
                            pq.push(v);
                        }
                    }
                    it++;
                }
            }
            cout << ans[y] + 1 << '\n';
        }
    }
    return 0;
}
