#include<bits/stdc++.h>


struct pq_pro_max {
    std::priority_queue<int, std::vector<int>, std::greater<>> pq, pqdel;
    void erase(int x) {
        pqdel.push(x); 
    }
    void insert(int x) {
        pq.push(x);
    }
    int size() {
        return pq.size() - pqdel.size();
    }
    void normalize() {
        while (pqdel.size() && pq.top() == pqdel.top()) pq.pop(), pqdel.pop();
    }
    int top() {
        normalize();
        return pq.top();
    }
    void pop() {
        normalize();
        pq.pop();
    }
};


int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto& i : a) std::cin >> i, --i;
    std::vector<int> t(n), who(n);
    auto lesgo = [&]() -> void {
        std::vector<std::vector<int>> fst(n);
        for (int i = n - 1; i >= 0; --i) {
            fst[a[i]].push_back(i);
        }
        std::fill(t.begin(), t.end(), -1);
        pq_pro_max pq;
        for (int i = 0; i < n; ++i) {
            if (fst[i].size()) pq.insert(fst[i].back());
        }
        for (int i = 0, j = 0; i < n; ++i) {
            if (t[i] != -1) continue;
            if (j == 0) {
                who[j] = i;
                t[i] = j++;
            } else {
                if (a[who[j - 1]] == a[i]) {
                    if (pq.size() == 1) {
                        who[j] = i;
                        t[i] = j++;
                    } else {
                        int k;
                        if (pq.top() == i) {
                            pq.pop();
                            k = pq.top();
                            pq.insert(i);
                        } else {
                            k = pq.top();
                        }
                        who[j] = k;
                        t[k] = j++;
                        pq.erase(k);
                        fst[a[k]].pop_back();
                        if (fst[a[k]].size()) pq.insert(fst[a[k]].back());
                        who[j] = i;
                        t[i] = j++;
                    }
                } else {
                    who[j] = i;
                    t[i] = j++;
                }
            }
            pq.erase(i);
            fst[a[i]].pop_back();
            if (fst[a[i]].size()) pq.insert(fst[a[i]].back());
        }
        for (int i = 0; i < n; ++i) who[t[i]] = i;
    };
    lesgo();
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int k;
            std::cin >> k;
            --k;
            std::swap(a[k], a[k + 1]);
            lesgo();
        } else {
            int k;
            std::cin >> k;
            --k;
            std::cout << t[k] + 1 << '\n';
        }
    }
}