#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll inf = 2e18;
const ld eps = 1e-13;
using vl = vector<ll>;
using vvl = vector<vl>;
const int block_sz = 3;
struct Segtree {
    struct Node {
        ll min;
    };
    Node null {
        inf
    };
    vector<ll> a;
    vector<Node> t;
    Segtree(vector<ll> &a_) {
        a = a_;
        t.assign((ll)a.size() * 4, null);
        build(0, 0, (ll)a.size());
    }
    Node mergee(Node a, Node b) {
        Node ans;
        ans.min = min(a.min, b.min);
        return ans;
    }
    void build(ll v, ll tl, ll tr) {
        if (tl + 1 == tr) {
            t[v].min = a[tl];
            return;
        }
        ll tm = (tl + tr) / 2;
        build(v*2+1, tl, tm);
        build(v*2+2, tm, tr);
        t[v] = mergee(t[v*2+1], t[v*2+2]);
    }
    void ins(ll v, ll indx, ll val, ll tl, ll tr) {
        if (tl + 1 == tr) {
            t[v].min = val;
            return;
        }
        ll tm = (tl + tr) / 2;
        if (tm > indx) {
            ins(v*2+1, indx, val, tl, tm);
        } else {
            ins(v*2+2, indx, val, tm, tr);
        }
        t[v] = mergee(t[v*2+1], t[v*2+2]);
    }
    Node query(ll v, ll l, ll r, ll tl, ll tr) {
        if (l >= tr || tl >= r) return null;
        if (tl + 1 == tr) return t[v];
        ll tm = (tl + tr) / 2;
        return mergee(query(v*2+1, l, r, tl, tm), query(v*2+2, l, r, tm, tr));
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll n, q; cin >> n >> q;
    vector<ll> help(n);
    for (auto &i : help) cin >> i;
    vector<ll> a(n, -1);
    vector<ll> calc(n, -1);
    vector<ll> a_rev(n, -1);
    map<ll, vector<ll>> mp;
    ll sz = n + 1;
    auto calc_all = [&]() {
        a.assign(n, -1);
        a_rev.assign(n, -1);
        calc.assign(n, -1);
        mp.clear();
        for (ll i = 0; i < n; i++) {
            mp[help[i]].push_back(i);
        }
        for (auto &[_, i] : mp) reverse(i.begin(), i.end());
        vector<ll> trash(sz, inf);
        Segtree t(trash);
        for (auto &[j, i] : mp) {
            t.ins(0, j, (i.empty() ? inf : i.back()), 0, sz);
        }
        ll el = 0;
        while (true) {
            ll val = help[el];
            mp[val].pop_back();
            t.ins(0, val, (mp[val].empty() ? inf : mp[val].back()), 0, sz);
            t.ins(0, val, inf, 0, sz);
            if (t.t[0].min == inf) {
                t.ins(0, val, (mp[val].empty() ? inf : mp[val].back()), 0, sz);
            }
            if (t.t[0].min == inf) {
                break;
            }
            a[el] = t.t[0].min;
            el = t.t[0].min;
            t.ins(0, val, (mp[val].empty() ? inf : mp[val].back()), 0, sz);
        }
        for (ll i = 0; i < n; i++) {
            if (a[i] != -1) a_rev[a[i]] = i;
        }
        for (ll i = 0; i < n; i++) {
            ll curr = i;
            for (ll j = 0; j <= block_sz; j++) {
                calc[i] = curr;
                if (curr == -1) break;
                curr = a_rev[curr];
            }
        }
    };
    calc_all();
//    for (auto &i : a) cout << i << " ";
//    cout << "\n";
    while (q--) {
        ll tp; cin >> tp;
        if (tp == 2) {
            ll indx; cin >> indx;
            indx--;
            ll ans = 0;
            ll curr = indx;
            while (calc[curr] != -1) {
                ans += block_sz;
                curr = calc[curr];
            }
            while (curr != -1) {
                curr = a_rev[curr];
                ans++;
            }
            cout << ans << "\n";
        } else {
            ll indx; cin >> indx;
            indx--;
            swap(help[indx], help[indx + 1]);
            calc_all();
        }
    }
}
