#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

constexpr int sz = 500'000;
std::set<int> arr[sz + 1];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, q;
    std::cin >> n >> q;
    std::set<std::pair<int, int>> st;
    std::vector<int> x(n);
    for (int i = 0; i < n; i++) std::cin >> x[i];
    for (int i = n - 1; i >= 0; i--) {
        if (!arr[x[i]].empty()) {
            st.erase(std::make_pair(*arr[x[i]].begin(), x[i]));
        }
        arr[x[i]].insert(i);
        st.insert(std::make_pair(*arr[x[i]].begin(), x[i]));
    }
    for (int hg = 0; hg < q; hg++) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int xi;
            std::cin >> xi;
            xi--;
            st.erase(std::make_pair(*arr[x[xi]].begin(), x[xi]));

            st.erase(std::make_pair(*arr[x[xi + 1]].begin(), x[xi + 1]));
            arr[x[xi]].erase(xi);
            arr[x[xi + 1]].erase(xi + 1);
            std::swap(x[xi], x[xi + 1]);
            arr[x[xi]].insert(xi);
            arr[x[xi + 1]].insert(xi + 1);

            st.insert(std::make_pair(*arr[x[xi]].begin(), x[xi]));
            st.insert(std::make_pair(*arr[x[xi + 1]].begin(), x[xi + 1]));
        } else {
            int yi;
            std::set<std::pair<int, int>> cp = st;
            std::cin >> yi;
            yi--;
            int start = 0, ind = 0;
            cp.erase(cp.begin());
            if (!arr[x[0]].empty()) {
                if (arr[x[0]].size() > 1) cp.insert(std::make_pair(*(++arr[x[0]].begin()), x[0]));
            }
            while (start != yi) {
                ind++;
                if (cp.size() == 1) {
                    start = cp.begin()->first;
                    cp.erase(cp.begin());
                    auto it = arr[x[start]].upper_bound(start);
                    if (it != arr[x[start]].end()) {
                        cp.insert(std::make_pair(*it, x[start]));
                    }
                } else {
                    auto it = (cp.begin()->second == x[start] ? (++cp.begin()) : (cp.begin()));
                    auto cppair = *it;
                    auto it2 = arr[cppair.second].upper_bound(cppair.first);
                    cp.erase(it);
                    if (it2 != arr[cppair.second].end()) {
                        cp.insert(std::make_pair(*it2, cppair.second));
                    }
                    start = cppair.first;
                }
            }
            std::cout << (ind + 1) << '\n';

        }
    }
}
