#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct Tree {
    vector<int> tree;
    int size = 1;

    void build(int n) {
        while (size < n) size <<= 1;
        tree.assign(2 * size - 1, 1e9);
    }

    void set(int i, int v) {
        set(0, size, 0, i, v);
    }

    void set(int l, int r, int x, int i, int v) {
        if (r - l > 1) {
            int m = (r + l) / 2;
            if (i < m) set(l, m, 2 * x + 1, i, v);
            else set(m, r, 2 * x + 2, i, v);
            tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
        } else tree[x] = v;
    }

    int get(int l, int r) {
        return get(0, size, 0, l, r);
    }

    int get(int l, int r, int x, int L, int R) {
        if (L <= l && r <= R) return tree[x];
        else if (R <= l || r <= L) return 1e9;
        else {
            int m = (r + l) / 2;
            return min(get(l, m, 2 * x + 1, L, R),
                       get(m, r, 2 * x + 2, L, R));
        }
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    vector<deque<int>> cnt(n + 1);
    for (auto &i: a) cin >> i;

    Tree tree;
    tree.build(n + 1);
    for (int i = 1; i < n; ++i) {
        if (cnt[a[i]].empty()) tree.set(a[i], i);
        cnt[a[i]].push_back(i);
    }

    vector<int> ans(n);
    int last = a[0];
    ans[0] = 1;

    for (int timee = 2; timee <= n; ++timee) {
        int next = min(tree.get(0, last), tree.get(last + 1, n + 1));

        if (next == -1 || next == 1e9) {
            ans[cnt[last].front()] = timee;
            cnt[last].pop_front();
            continue;
        }

        ans[next] = timee;

        cnt[a[next]].pop_front();
        if (cnt[a[next]].empty()) tree.set(a[next], 1e9);
        else tree.set(a[next], cnt[a[next]].front());

        last = a[next];
    }

    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int x;
            cin >> x;
            if (a[x - 1] == a[x]) continue;
            swap(a[x - 1], a[x]);

            tree.build(n + 1);
            last = a[0];
            ans[0] = 1;

            for (int i = 1; i < n; ++i) {
                if (cnt[a[i]].empty()) tree.set(a[i], i);
                cnt[a[i]].push_back(i);
            }

            for (int timee = 2; timee <= n; ++timee) {
                int next = min(tree.get(0, last), tree.get(last + 1, n + 1));

                if (next == -1 || next == 1e9) {
                    ans[cnt[last].front()] = timee;
                    cnt[last].pop_front();
                    continue;
                }

                ans[next] = timee;

                cnt[a[next]].pop_front();
                if (cnt[a[next]].empty()) tree.set(a[next], 1e9);
                else tree.set(a[next], cnt[a[next]].front());

                last = a[next];
            }
        } else {
            int y;
            cin >> y, y--;
            cout << ans[y] << "\n";
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) solve();
}