#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using ld = long double;

short tree[20001];

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

int get(int v, int l, int r, int ql, int qr) {
    if (qr <= l || r <= ql) return 1e9;
    if (ql <= l && r <= qr) return tree[v];
    int m = (l + r) / 2;
    return min(get(v * 2, l, m, ql, qr), get(v * 2 + 1, m, r, ql, qr));
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<short> a(n);
    for (auto &el : a) cin >> el;
    vector<deque<short>> ind(n);
    for (int i = 0; i < n; ++i) {
        ind[a[i] - 1].pb(i);
    }
    for (int i = 0; i < q; ++i) {
        int t, j;
        cin >> t >> j;
        j--;
        if (t == 1) {
            if (a[j] != a[j + 1]) {
                int bi = lower_bound(all(ind[a[j] - 1]), j) - ind[a[j] - 1].begin();
                int ci = lower_bound(all(ind[a[j + 1] - 1]), j) - ind[a[j + 1] - 1].begin();
                //cout << a[j] << ' ' << a[j + 1] << endl;
                //cout << bi << ' ' << ci << ' ' << ind[a[j] - 1].size() << ' ' << ind[a[j + 1] - 1].size() << endl;
                swap(ind[a[j] - 1][bi], ind[a[j + 1] - 1][ci]);
                swap(a[j], a[j + 1]);
            }
        } else {
            fill(tree, tree + 20001, 5010);
            for (int i = 0; i < n; ++i) {
                if (!ind[i].empty()) {
                    update(1, 0, n, i, ind[i][0]);
                }
            }
            int lst = a[0];
            vector<deque<short>> indc = ind;
            indc[a[0] - 1].pop_front();
            if (!indc[a[0] - 1].empty()) {
                update(1, 0, n, a[0] - 1, indc[a[0] - 1][0]);
            } else {
                update(1, 0, n, a[0] - 1, 5010);
            }
            if (j == 0) {
                cout << 1 << "\n";
            } else {
                int li = 0;
                int ans = 1;
                while (li != j) {
                    ans++;
                    int mn = min(get(1, 0, n, 0, lst - 1), get(1, 0, n, lst, n));
                    if (mn == 5010) {
                        li = indc[lst - 1][0];
                        indc[lst - 1].pop_front();
                    } else {
                        li = indc[a[mn] - 1][0];
                        lst = a[mn];
                        indc[lst - 1].pop_front();
                        if (indc[lst - 1].empty()) {
                            update(1, 0, n, lst - 1, 5010);
                        } else {
                            update(1, 0, n, lst - 1, indc[lst - 1][0]);
                        }
                    }
                }
                cout << ans << "\n";
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
}
