#include<iostream>
#include<set>
#pragma GCC target("avx2")
using namespace std;

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nuintptr);
    
    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<int, pair<set<int>, int>>> st;
            ps[a[1]].erase(1);
            for (int i = 1; i <= n; ++i)
                if (!ps[i].empty())
                    st.insert({ *ps[i].begin(), { ps[i], i } });
            ps[a[1]].insert(1);

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

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

                auto p = (*it).second;
                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.begin(), { nw, c } });
                ++ind; col = c;
            }
        }
    }

    return 0;
}