#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
pair<int, int> t[20000];


struct segtree {
    segtree() {}

    void build(int v, int tl, int tr, const vector<int> &a) {
        if (tr - tl > 1) {
            int tm = (tl + tr) / 2;
            build(2 * v + 1, tl, tm, a);
            build(2 * v + 2, tm, tr, a);
            t[v] = min(t[2 * v + 1], t[2 * v + 2]);
        } else
            t[v] = pair<int, int>(a[tl], tl);
    }

    pair<int, int> get(int v, int tl, int tr, int ql, int qr) const {
        if (tl >= qr || tr <= ql)
            return pair<int, int>(1e9, -1);
        if (tl >= ql && tr <= qr)
            return t[v];
        int tm = (tl + tr) / 2;
        return min(get(2 * v + 1, tl, tm, ql, qr), get(2 * v + 2, tm, tr, ql, qr));
    }

    void update(int v, int tl, int tr, int i, int x) {
        if (tl > i || tr <= i)
            return;
        if (tr - tl == 1) {
            t[v] = pair<int, int>(x, i);
            return;
        }
        int tm = (tl + tr) / 2;
        if (i < tm)
            update(2 * v + 1, tl, tm, i, x);
        else
            update(2 * v + 2, tm, tr, i, x);
        t[v] = min(t[2 * v + 1], t[2 * v + 2]);
    }
};


void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<queue<int>> b(n);
    vector<int> c(n);
    vector<int> ans(n);
    segtree st;

    while (q--) {
        int cmd, p;
        cin >> cmd >> p;
        p--;
        if (cmd == 1) {
            swap(a[p], a[p + 1]);
            continue;
        }

        for (int i = 0; i < n; i++)
            b[a[i]].push(i);
        for (int i = 0; i < n; i++)
            if (!b[i].empty())
                c[i] = b[i].front();
            else
                c[i] = 1e9;
        st.build(0, 0, n, c);

        int pc = -1;
        int i;
        for (i = 0; i < n; i++) {
            auto res = min(st.get(0, 0, n, 0, pc), st.get(0, 0, n, pc + 1, n));
            if (res.first == 1e9)
                break;
            ans[res.first] = i;
            pc = a[res.first];
            b[res.second].pop();
            if (!b[res.second].empty())
                st.update(0, 0, n, res.second, b[res.second].front());
            else
                st.update(0, 0, n, res.second, 1e9);
        }
        if (pc == -1)
            pc = a[0];
        for (; i < n; i++) {
            ans[b[pc].front()] = i;
            b[pc].pop();
        }
        cout << ans[p] + 1 << '\n';
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();
    return 0;
}
