#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

// #define int long long
#pragma GCC optimize("O3, unroll-loops")
#pragma GCC target("avx2")

// using namespace __gnu_pbds;
using ll = long long;
using namespace std;

// template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int> f(int n, vector<int> &a) {
    int ind = 0;
    set<vector<int>> st;
    vector<int> cur, ans(n, -1);
    vector<vector<int>> used(n + 1);
    for (int i = 0; i < n; i++) {
        used[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i].empty()) {
            st.insert({used[i][0], i, 0});
        }
    }
    while (!st.empty()) {
        auto z = *st.begin();
        st.erase(st.begin());
        int ind1 = z[0], col = z[1], ind2 = z[2];
        if (st.empty() || cur.empty() || cur.back() != col) {
            ans[ind1] = cur.size();
            cur.push_back(col);
            if (ind2 + 1 != used[col].size()) {
                st.insert({used[col][ind2 + 1], col, ind2 + 1});
            }
            continue;
        }
        auto z2 = *st.begin();
        st.erase(st.begin());
        ind1 = z2[0];col = z2[1];ind2 = z2[2];
        ans[ind1] = cur.size();
        cur.push_back(col);
        if (ind2 + 1 != used[col].size()) {
            st.insert({used[col][ind2 + 1], col, ind2 + 1});
        }
        st.insert(z);
    }
    return ans;
}

void solve() {
    int n, q, mn;
    cin >> n >> q;
    mn = n;
    vector<int> ans, a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ans = f(n, a);
    while (q--) {
        int t, ind;
        cin >> t >> ind;
        ind--;
        if (t == 1) {
            swap(a[ind], a[ind + 1]);
            mn = min(mn, ind);
        } else {
            if (ind >= mn) {
                ans = f(n, a);
                mn = n;
            }
            cout << ans[ind] + 1 << "\n";
        }
    }
}

signed main() {
    int t = 1;
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    // cin >> t;
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    // cin >> t;
    while (t--) {
        solve();
    }
}