#include <bits/stdc++.h>

using ll = long long;

using namespace std;

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<ll> A(n);
    for (ll i = 0; i < n; i++) {
        cin >> A[i];
    }
    vector<ll> Ans(n);
    ll f = -1;
    f = 1;
    unordered_map<ll, vector<ll> > D;
    unordered_map<ll, ll> L;
    for (ll j = 0; j < n; j++) {
        D[A[j]].push_back(j);
    }
    set<pair<ll, ll> > I;
    for (auto j: D) {
        if (L[j.first] == D[j.first].size()) {
            continue;
        }
        I.insert({D[j.first][L[j.first]], j.first});
        L[j.first]++;
    }
    ll pr = -1, p = 0;
    while (I.size() > 0) {
        p++;
        auto x = I.begin();
        if (I.size() == 1) {
            Ans[x->first] = p;
            //cout << x->second << '\n';
            if (L[x->second] >= D[x->second].size()) {
                pr = x->second;
                I.erase(x);
                continue;
            }
            auto x1 = *x;
            pr = x->second;
            I.erase(x1);
            I.insert({D[x1.second][L[x1.second]], x1.second});
            L[x1.second]++;
            continue;
        }
        if (x->second == pr) {
            x++;
        }
        Ans[x->first] = p;
        if (L[x->second] >= D[x->second].size()) {
            pr = x->second;
            I.erase(x);
            continue;
        }
        auto x1 = *x;
        I.erase(x1);
        I.insert({D[x1.second][L[x1.second]], x1.second});
        L[x1.second]++;
        pr = x1.second;
    }
    for (ll i = 0; i < q; i++) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll x;
            cin >> x;
            swap(A[x], A[x - 1]);
            f = -1;
        } else {
            ll a;
            cin >> a;
            a--;
            if (f != -1) {
                cout << Ans[a] << '\n';
                continue;
            }
            f = 1;
            unordered_map<ll, vector<ll> > D;
            unordered_map<ll, ll> L;
            for (ll j = 0; j < n; j++) {
                D[A[j]].push_back(j);
            }
            set<pair<ll, ll> > I;
            for (auto j: D) {
                if (L[j.first] == D[j.first].size()) {
                    continue;
                }
                I.insert({D[j.first][L[j.first]], j.first});
                L[j.first]++;
            }
            ll pr = -1, p = 0;
            while (I.size() > 0) {
                p++;
                auto x = I.begin();
                if (I.size() == 1) {
                    Ans[x->first] = p;
                    //cout << x->second << '\n';
                    if (L[x->second] >= D[x->second].size()) {
                        pr = x->second;
                        I.erase(x);
                        continue;
                    }
                    auto x1 = *x;
                    pr = x->second;
                    I.erase(x1);
                    I.insert({D[x1.second][L[x1.second]], x1.second});
                    L[x1.second]++;
                    continue;
                }
                if (x->second == pr) {
                    x++;
                }
                Ans[x->first] = p;
                if (L[x->second] >= D[x->second].size()) {
                    pr = x->second;
                    I.erase(x);
                    continue;
                }
                auto x1 = *x;
                I.erase(x1);
                I.insert({D[x1.second][L[x1.second]], x1.second});
                L[x1.second]++;
                pr = x1.second;
            }
            cout << Ans[a] << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    //cin >> t;
    for (ll i = 0; i < t; i++) {
        solve();
    }
    return 0;
}
