#include<iostream>
#include<set>
#pragma GCC optimize("Ofast")
using namespace std;

using ll = long long;
using ld = long double;

const ll infl = (ll)4e18 + 100;
const int infi = (int)1e9 + 100;
const int maxn = (int)1e6 + 10;
const int mod = (int)1e9 + 7;

int n, q, a[maxn];
set<int> ps[maxn];

inline void solve() {
    cin >> n >> q;
    // cout << "ps:\n";
    // for (int i = 1; i <= n; ++i) {
    //     cout << i << ": ";
    //     for (auto& el : ps[a[i]])
    //         cout << el << " ";
    //     cout << '\n';
    // }
    // cout << "--------------\n";
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; // cout << a[i] << "<<<<<<<<<<\n";
        ps[a[i]].insert(i);

        // cout << "ps:\n";
        // for (int i = 1; i <= n; ++i) {
        //     cout << i << ": ";
        //     for (auto& el : ps[a[i]])
        //         cout << el << " ";
        //     cout << '\n';
        // }
        // cout << "--------------\n";
    }

    while (q--) {
        int tp; cin >> tp;
        if (tp == 1) {
            int x; cin >> x;

            if (a[x] != a[x + 1]) {
                ps[a[x]].erase(x); ps[a[x + 1]].erase(x + 1);
                swap(a[x], a[x + 1]);
                ps[a[x]].insert(x); ps[a[x + 1]].insert(x + 1);
            }
        }
        else {
            int y; cin >> y;

            if (y == 1) {
                cout << 1 << '\n';
                continue;
            }

            set<pair<set<int>, int>> st;
            ps[a[0]].erase(0);
            for (int i = 1; i < n; ++i)
                if (!ps[i].empty())
                    st.insert({ ps[i], i });
            ps[a[0]].insert(0);

            int ind = 1, col = a[0];
            while (true) {
                auto it = st.begin();
                while (it != st.end() && (*it).second == col)
                    ++it;

                if (it == st.end())
                    it = st.begin();

                auto p = *it;
                auto nw = p.first;
                auto c = p.second;

                st.erase(it);

                if (*nw.begin() == y) {
                    cout << ind << '\n';
                    break;
                }

                nw.erase(nw.begin());
                if (!nw.empty())
                    st.insert({ nw, c });
                ++ind; col = c;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t_ = 1; // cin >> t_;
    while (t_--) {
        solve();
        cout << '\n';
    }

    return 0;
}