 // hello, it is a very good problem
#include <bits/stdc++.h>

using namespace std;
vector<int> build(int n, vector<int>a) {
    vector<int> ans(n);
    set<int> s;
    for (int i = 0; i <= n; ++i) {
        s.insert(i);
    }
    int prc = -1, ima = -1, pr;
    for (int i = 0; i < n; ++i) {
        int mi = (*s.begin());
        if (a[mi] != prc) {
            ans[mi] = i;
            prc = a[mi];
            s.erase(mi);
            if (i != n - 1 && a[*s.begin()] != prc) {
                ima = -1;
            }
        } else {
            if (ima == -1) ima = mi;
            while (ima < n && a[ima] == prc) {
                auto it = s.find(ima);
                it++;
                ima = (*it);
            }
            if (ima == n) {
                ans[mi] = i;
                s.erase(mi);
            } else {
                ans[ima] = i;
                prc = a[ima];
                auto it = s.find(ima);
                it++;
                pr = ima;
                ima = (*it);
                s.erase(pr);
            }
        }
    }
    return ans;
}
int main() {
    int n, q;
    cin >> n >> q;
    vector<int>a(n), ans(n);
    for (auto&u : a) cin >> u;
    ans = build(n, a);
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            swap(a[x - 1], a[x]);
            ans = build(n, a);
        } else {
            cout << ans[x - 1] + 1 << '\n';
        }
    }
}
