#include <bits/stdc++.h>
#pragma optimize "O3"
#pragma optimize "fast-math"
#pragma optimize "unrool-loops"
using namespace std;
using ll = long long;
using vint = vector<int>;
using pii = pair<int, int>;
const int INF = 1 << 30;

struct Node2 {
    int mn, ind;
};

struct SegTree2 {
    int sz;
    vector<Node2> tree;
    Node2 ZERO = {INF, INF};

    static Node2 combine(const Node2 a, const Node2 b) {
        if (a.mn < b.mn) {
            return a;
        }
        return b;
    }

    SegTree2(int n, vint &v) {
        sz = 1;
        while (sz < n) {
            sz <<= 1;
        }
        tree.assign(2 * sz - 1, ZERO);

        for (int i = 0; i < n; i++) {
            tree[i + sz - 1].mn = v[i];
            tree[i + sz - 1].ind = i;
        }
        for (int i = sz - 2; i >= 0; i--) {
            tree[i] = combine(tree[2 * i + 1], tree[2 * i + 2]);
        }
    }

    Node2 mn(const int x, const int lx, const int rx, const int l, const int r) {
        if (lx >= r || rx <= l) {
            return ZERO;
        }
        if (lx >= l && rx <= r) {
            return tree[x];
        }
        int mid = (lx + rx) / 2;
        int a = 2 * x + 1;
        int b = a + 1;
        return combine(mn(a, lx, mid, l, r), mn(b, mid, rx, l, r));
    }

    Node2 mn(const int l, const int r) {
        if (l == r) {
            return ZERO;
        }
        return mn(0, 0, sz, l, r);
    }

    void st(const int x, const int lx, const int rx, const int ind, const int val) {
        if (rx - lx == 1) {
            tree[x].mn = val;
            return;
        }
        int mid = (lx + rx) / 2;
        int a = 2 * x + 1;
        int b = a + 1;
        if (ind < mid) {
            st(a, lx, mid, ind, val);
        } else {
            st(b, mid, rx, ind, val);
        }
        tree[x] = combine(tree[a], tree[b]);
    }

    void st(const int ind, const int val) {
        st(0, 0, sz, ind, val);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vint v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        v[i]--;
    }
    while (q--) {
        int o, rer;
        cin >> o >> rer;
        rer--;
        if (o == 1) {
            swap(v[rer], v[rer + 1]);
        } else {
            if (rer == 0) {
                cout << 1 << '\n';
                continue;
            }
            vint a(n);
            vector<vint> t(n);
            for (int i = 0; i < n; i++) {
                t[v[i]].push_back(i);
            }
            vint y(n, INF);
            for (int i = 0; i < n; i++) {
                if (t[i].empty()) {
                    continue;
                }
                sort(t[i].begin(), t[i].end(), greater<int>());
                y[i] = t[i].back();
            }
            a[0] = 0;
            if (t[v[0]].size() == 1) {
                y[v[0]] = INF;
            } else {
                t[v[0]].pop_back();
                y[v[0]] = t[v[0]].back();
            }
            SegTree2 st2(n, y);
            int p = 0;
            for (int i = 0; i < n - 1; i++) {
                const Node2 q1 = st2.mn(0, v[p]);
                const Node2 q2 = st2.mn(v[p] + 1, n);
                 Node2 x = st2.combine(q1, q2);
                if (x.mn == INF) {
                    x.ind = v[p];
                }
                const int ind = x.ind;
                a[t[ind].back()] = i + 1;
                if (t[ind].back() == rer) {
                    cout << i + 2 << '\n';
                    break;
                }
                p = t[ind].back();
                t[ind].pop_back();
                if (t[ind].empty()) {
                    st2.st(ind, INF);
                } else {
                    st2.st(ind, t[ind].back());
                }
            }
        }
    }
}

//
//5 10
//3 1 1 2 2
