#pragma GCC optimize("O3")

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;

struct SegTree {
    vector<pair<int, int>> tree;
    void build(int p, int l, int r, vector<int>& a) {
        if (r - l == 1) {
            tree[p] = {a[l], l};
            return;
        }
        int m = (l + r) / 2;
        build(2 * p + 1, l, m, a);
        build(2 * p + 2, m, r, a);
        tree[p] = min(tree[2 * p + 1], tree[2 * p + 2]);
    }
    void update(int p, int l, int r, int i, int x) {
        if (r - l == 1) {
            tree[p] = {x, i};
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            update(2 * p + 1, l, m, i, x);
        } else {
            update(2 * p + 2, m, r, i, x);
        }
        tree[p] = min(tree[2 * p + 1], tree[2 * p + 2]);
    }
    pair<int, int> get(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[p];
        if (l >= qr || r <= ql) return {1e9, -1};
        int m = (l + r) / 2;
        return min(get(2 * p + 1, l, m, ql, qr), get(2 * p + 2, m, r, ql, qr));
    }
    SegTree(vector<int>& a) {
        tree.resize(4 * a.size());
        build(0, 0, a.size(), a);
    }
};

int main() {
    #ifdef LOCAL
    freopen("_test.in", "r", stdin);
    freopen("_test.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<set<int>> sts(n + 1);
    for (int i = 1; i <= n; i++) {
        sts[a[i]].insert(i);
    }
    vector<int> mn(n + 1);
    for (int i = 1; i <= n; i++) {
        if (sts[i].size() == 0) {
            mn[i] = 1e9;
        } else {
            mn[i] = *sts[i].begin();
        }
    }

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            sts[a[x]].erase(x);
            sts[a[x + 1]].erase(x + 1);
            swap(a[x], a[x + 1]);
            sts[a[x]].insert(x);
            sts[a[x + 1]].insert(x + 1);
            mn[a[x]] = *sts[a[x]].begin();
            mn[a[x + 1]] = *sts[a[x + 1]].begin();
            continue;
        }

        auto sts_cur = sts;
        SegTree tree(mn);

        int y;
        cin >> y;
        if (y == 1) {
            cout << 1 << '\n';
            continue;
        }

        int last = 1;
        sts_cur[a[1]].erase(1);
        if (sts_cur[a[1]].size() == 0) {
            tree.update(0, 0, n + 1, a[1], 1e9);
        } else {
            tree.update(0, 0, n + 1, a[1], *sts_cur[a[1]].begin());
        }

        for (int time = 2; time <= n; time++) {
            int v = a[last];
            pair<int, int> mn_v = {1e9, -1};
            if (v != 1) mn_v = tree.get(0, 0, n + 1, 1, v);
            if (v != n) mn_v = min(mn_v, tree.get(0, 0, n + 1, v + 1, n + 1));

            if (y == mn_v.first) {
                cout << time << '\n';
                break;
            }

            if (mn_v.first == 1e9) {
                int cur = *sts_cur[a[last]].begin();
                if (cur == y) {
                    cout << time << '\n';
                    break;
                }
                sts_cur[a[last]].erase(cur);
                last = cur;
                continue;
            }

            sts_cur[mn_v.second].erase(mn_v.first);
            if (sts_cur[mn_v.second].size() == 0) {
                tree.update(0, 0, n + 1, mn_v.second, 1e9);
            } else {
                tree.update(0, 0, n + 1, mn_v.second, *sts_cur[mn_v.second].begin());
            }
            last = mn_v.first;
        }
    }
}