#include <bits/stdc++.h>

using namespace std;
using ll = long long;

signed main() {
    ll n, q;
    cin >> n >> q;
    vector<ll> v(n);
    for (ll i = 0; i < n; i++) cin >> v[i];
    vector<vector<ll> > pref(n, vector<ll>(n, 1e9)), pr(n, vector<ll>(n));
    vector<ll> p(n);
    for (ll i = 0; i < n; i++) {
        for (ll j = p[v[i]] + 1; j <= i; j++) {
            pref[j][v[i]] = i;
        }
        p[v[i]] = i;
    }
    for (ll j = 0; j < n; j++) {
        vector<ll> mn(n + 1, 1e9);
        ll m = 1e9;
        for (ll i = 0; i < n; i++) {
            m = min(pref[j][i], m);
            mn[i + 1] = m;
        }
        m = 1e9;
        pr[j][n - 1] = mn[n - 2];
        ll a = pref[j][n - 1];
        for (ll i = n - 2; i >= 0; i--) {
            pr[j][i] = min(a, mn[i]);
            a = min(a, pref[j][i]);
        }
    }
    while (q--) {
        ll t, x;
        cin >> t >> x;
        if (t == 1) {
            for (ll i = 0; i <= x; i++) {
                if (pr[i][v[x]] == x - 1) pr[i][v[x]]++;
                if (pr[i][v[x - 1]] == x) pr[i][v[x - 1]]--;
            }
            if (v[x] != v[x - 1]) pr[x][v[x]] = x;
            swap(v[x], v[x - 1]);
        } else {
            x--;
            if (x == 0) {
                cout << 1 << endl;
                continue;
            }
            ll cnt = 1, fl = v[0];
            vector<bool> w(n, false);
            ll i = 1;
            while (i < n) {
                if (w[i]) {
                    i++;
                    continue;
                }
                ll ind = pr[i][fl];
                if (ind == 1e9) {
                    w[i] = true;
                    ind = i;
                } else w[ind] = true;
                cnt++;
                fl = v[ind];
                if (ind == x) {
                    break;
                }
            }
            cout << cnt << endl;
        }
    }
}
