#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")

#define all(a) a.begin(), a.end()

struct node {
    int v, id;
    node(int _v = 1e9, int _id = 0) {
        v = _v;
        id = _id;
    }
};

node f(node &a, node &b) {
    if (a.v < b.v) {
        return a;
    }
    return b;
}

struct sgt {
    int n;
    vector<node> t;
    vector<int> p;

    void build(int v, int l, int r, vector<int> &a) {
        if (r-l == 1) {
            if (l < a.size()) {
                t[v].v = a[l];
                t[v].id = l;
            }
            return;
        }
        int m = (l+r)/2;
        build(2*v+1, l, m, a);
        build(2*v+2, m, r, a);
        t[v] = f(t[2*v+1], t[2*v+2]);
    }

    sgt(vector<int> &a) {
        n = 1;
        while (n < a.size()) {
            n *= 2;
        }
        t.assign(2*n-1, node());
        p.assign(2*n-1, -1);
        build(0, 0, n, a);
    }

    void apply(int v, int x) {
        t[v].v = x;
        p[v] = x;
    }

    void push(int v, int l, int r) {
        if (r-l == 1 || p[v] == -1) {
            return;
        }
        apply(2*v+1, p[v]);
        apply(2*v+2, p[v]);
        p[v] = -1;
    }

    node get(int v, int l, int r, int lq, int rq) {
        if (l >= lq && r <= rq) {
            return t[v];
        }
        if (r <= lq || rq <= l) {
            return node();
        }
        push(v, l, r);
        int m = (l+r)/2;
        node a = get(2*v+1, l, m, lq, rq);
        node b = get(2*v+2, m, r, lq, rq);
        return f(a, b);
    }

    node get(int l, int r) {
        r++;
        return get(0, 0, n, l, r);
    }

    void upd(int v, int l, int r, int lq, int rq, int x) {
        if (l >= lq && r <= rq) {
            apply(v, x);
            return;
        }
        if (r <= lq || rq <= l) {
            return;
        }
        push(v, l, r);
        int m = (l+r)/2;
        upd(2*v+1, l, m, lq, rq, x);
        upd(2*v+2, m, r, lq, rq, x);
        t[v] = f(t[2*v+1], t[2*v+2]);
    }

    void upd(int l, int r, int x) {
        r++;
        upd(0, 0, n, l, r, x);
    }
};

mt19937 rd;
uniform_int_distribution<> d(1, 4);
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<vector<int>> col(n+1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        col[a[i]].push_back(i);
    }

    vector<int> l(n+1);
    vector<int> uwu;
    for (int i = 1; i <= n; ++i) {
        l[i] = col[i].size();
        for (auto x : col[i]) {
            uwu.push_back(x);
        }
    }
    vector<int> pl(n+1);
    for (int i = 1; i <= n; ++i) {
        pl[i] = pl[i-1] + l[i];
    }
    sgt tree(uwu);
    vector<int> b(n);
    b[0] = 0;
    int c = 0;
    vector<int> ord(n);
    node a1 = tree.get(0, n-1);
    tree.upd(a1.id, a1.id, 1e9);
    int k = a1.v;
    b[k] = 0;
    c = a[k];
    ord[0] = k;
    for (int i = 1; i < n; ++i) {
        node a1 = tree.get(0, pl[c-1] - 1);
        node b1 = tree.get(pl[c], n-1);
        if (a1.v > b1.v) {
            a1 = b1;
        }
        if (a1.v > n) {
            a1 = tree.get(pl[c-1], pl[c] - 1);
        }
        tree.upd(a1.id, a1.id, 1e9);
        int k = a1.v;
        b[k] = i;
        c = a[k];
        ord[i] = k;
    }
    // for (int i = 0; i < n; ++i) {
    //     cerr << b[i] << " ";
    // }
    // cerr << endl;
    while (q--) {
        int t;
        cin >> t;
        int x;
        cin >> x;
        x--;
        //  int t = 1;
        //  uniform_int_distribution<> e(0, n-2);
        //  int x = e(rd);
        // cout << x << endl;
        if (t == 1) {
            if (a[x] != a[x+1]) {
                if (b[x] < b[x+1]) {
                    int f = b[x];
                    int c = 0;
                    if (f) {
                        c = a[ord[f-1]];
                    }
                    if (a[x+1] != c) {
                        int r = b[x+1] + 1;
                        int o = 0;
                        if (r < n && a[ord[r]] == a[x]) {
                            while (r < n-1 && (r== b[x+1]+1 || a[ord[r]] == a[ord[r-1]] || ord[r] > ord[r+1] && a[ord[r+1]] != a[ord[r-1]])) {
                                int f = ord[r];
                                int s = ord[r+1];
                                if (a[f] == a[s]) {
                                    break;
                                }
                                swap(b[f], b[s]);
                                swap(ord[r], ord[r+1]);
                                r += 2;
                            }
                        } else {
                            if (r < n-1 && a[ord[r+1]] == a[x+1] && ord[r] > ord[r+1]) {
                                int uwu = ord[r];
                                while (r < n-1 && (ord[r] == uwu || a[ord[r]] == a[ord[r-1]] || ord[r] > ord[r+1] && a[ord[r+1]] != a[ord[r-1]])) {
                                    int f = ord[r];
                                    int s = ord[r+1];
                                    if (a[f] == a[s]) {
                                        break;
                                    }
                                    swap(b[f], b[s]);
                                    swap(ord[r], ord[r+1]);
                                    r += 2;
                                }
                            }
                        }
                    }else {
                        swap(b[x],  b[x+1]);
                        swap(ord[b[x]], ord[b[x+1]]);
                    }
                }
                else {
                    swap(b[x], b[x+1]);
                    swap(ord[b[x]], ord[b[x+1]]);
                }
                swap(a[x], a[x+1]);
            }
            // for (int i = 0; i < n; ++i) {
            //     cerr << b[i] << " ";
            // }
            // cerr << endl;
        }else {
            cout << b[x]+1 << ' ';
        }
        // vector<int> w = b;
        // vector<int> b(n);
        // b[0] = 0;
        // vector<int> used(n);
        // used[0] = 1;
        // int c = a[0];
        // for (int i = 1; i < n; ++i) {
        //     int k = -1;
        //     for (int j = 0; j < n; ++j) {
        //         if (!used[j]) {
        //             if (a[j] != c) {
        //                 k = j;
        //                 break;
        //             }
        //         }
        //     }
        //     if (k != -1) {
        //         used[k] = 1;
        //         b[k] = i;
        //         c = a[k];
        //     }else {
        //         for (int j = 0; j < n; ++j) {
        //             if (!used[j]) {
        //                 k = j;
        //                 break;
        //             }
        //         }
        //         b[k] = i;
        //         used[k] = 1;
        //     }
        // }
        // if (w != b) {
        //     for (auto x : b) {
        //         cout << x << " ";
        //     }
        //     cout << "\nstop";
        //     return;
        // }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << '\n';
    }
}