//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2,avx,bmi")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// using ordered_set  = tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct node {
    int val = INT_MAX, id;
};

struct segtree {
    vector<node> t;

    node merge(node &a, node &b) {
        if (a.val < b.val) return a;
        return b;
    }

    void upd(int v, int tl, int tr, int pos, int x) {
        if (tl + 1 == tr) {
            t[v].val = x;
            t[v].id = tl;
            return;
        }
        if (pos < (tl + tr) / 2) {
            upd(v * 2, tl, (tl + tr) / 2, pos, x);
        } else {
            upd(v * 2 + 1, (tl + tr) / 2, tr, pos, x);
        }
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }

    node get(int v, int tl, int tr, int ql, int qr) {
        if (qr <= tl || tr <= ql) return node();
        if (ql <= tl && tr <= qr) return t[v];
        node L=get(v * 2, tl, (tl + tr) / 2, ql, qr),R=get(v * 2 + 1, (tl + tr) / 2, tr, ql, qr);
        return merge(L, R);
    }
};


signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //cout<<3;
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    vector<vector<int>> st(n + 1, {0, 0, 0});
    auto calc = [&]() -> void {
        deque<deque<int>> pos(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (i > 1) pos[a[i]].push_back(i);
        }
        segtree A;
        A.t.resize(4 * (n + 1));
        for (int i = 1; i <= n; ++i) {
            if (pos[i].empty()) {
                A.upd(1, 1, n + 1, i, INT_MAX);
                continue;
            }
            A.upd(1, 1, n + 1, i, pos[i].front());
        }
        int cur = 1, cnt = 0, pr = 0;
        while (cnt < n) {
            //cout<<cnt<<' '<<cur<<endl;
            //if (cur > n) exit(12);
            st[cur][0] = pr;
            st[cur][2] = cnt+1;
//        pos[a[cur]].pop_front();
//        if (pos[a[cur]].size()) {
//            A.upd(1, 1, n + 1, a[cur], pos[a[cur]].front());
//        } else {
//            A.upd(1, 1, n + 1, a[cur], INT_MAX);
//        }
            //cout << cnt << ' ' <<cur<< endl;
            node L = A.get(1, 1, n + 1, 1, a[cur]), R = A.get(1, 1, n + 1, a[cur] + 1, n + 1);
            if (R.val < L.val) L = R;
            if (L.val == INT_MAX) {
                //cout<<cnt<<' '<<a[cur]<<endl;
                if (cnt + 1 == n) {
                    st[cur][1] = n + 1;
                } else {
                    st[cur][1] = pos[a[cur]].front();
                    pos[a[cur]].pop_front();
                }
            } else {
                //cout<<"add"<<endl;
                //cout<<L.val<<' '<<L.id<<endl;
                int p = L.id;
                st[cur][1] = pos[p].front();
                pos[p].pop_front();
                if (pos[p].size()) {
                    A.upd(1, 1, n + 1, p, pos[p].front());
                } else {
                    A.upd(1, 1, n + 1, p, INT_MAX);
                }
            }
            pr = cur;
            cur = st[cur][1];
            cnt++;
        }
    };
//    for (int i = 1; i <= n; ++i) {
//        cout << st[i][0] << ' ' << st[i][1] << ' ' << st[i][2] << '\n';
//    }
//    return 0;
    calc();
    int pw = 1;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int p;
            cin >> p;
            swap(a[p], a[p + 1]);
            pw = 0;
        } else {
            int p;
            cin >> p;
            if (!pw) calc();
            pw = 1;
            cout << st[p][2] << '\n';
        }
        //cout<<"OK"<<endl;
    }
}



