#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll INF = 2e18;

struct ST {
    ll n, nt = INF;
    vector<ll> t;

    ll merge(ll a, ll b) {
        return min(a, b);
    }

    ST(vector<ll> &a) {
        n = (ll) a.size();
        t.resize(4 * n);
        build(0, 0, n, a);
    }

    void build(ll v, ll tl, ll tr, vector<ll> &a) {
        if (tl + 1 == tr) {
            t[v] = a[tl];
            return;
        }
        ll tm = (tl + tr) >> 1;
        build(2 * v + 1, tl, tm, a);
        build(2 * v + 2, tm, tr, a);
        t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
    }

    void update(ll v, ll tl, ll tr, ll idx, ll x) {
        if (tl + 1 == tr) {
            t[v] = x;
            return;
        }
        ll tm = (tl + tr) >> 1;
        update(2 * v + 1, tl, tm, idx, x);
        update(2 * v + 2, tm, tr, idx, x);
        t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
    }

    void upd(ll idx, ll x) {
        update(0, 0, n, idx, x);
    }

    ll gett(ll v, ll tl, ll tr, ll l, ll r) {
        if (l <= tl && tr <= r) return t[v];
        if (tl >= r || tr <= l) return nt;
        ll tm = (tl + tr) >> 1;
        return merge(gett(2 * v + 1, tl, tm, l, r), gett(2 * v + 2, tm, tr, l, r));
    }

    ll get(ll l, ll r) {
        return gett(0, 0, n, l, r);
    }
};

void solve() {
    ll n, q;
    cin >> n >> q;
    auto get = [&](vector<ll> &a, ll id) -> ll {
        // for (auto &i: a) cerr << i << ' ';
        // cerr << '\n';
        // vector<vector<ll> > idx(n);
        // vector<ll> cur(n), fi(n, INF);
        // for (int i = 0; i < n; ++i) {
        //     if (fi[a[i]] == INF) fi[a[i]] = i;
        //     idx[a[i]].push_back(i);
        // }
        // // for (auto &i: fi) cerr << i << ' ';
        // // cerr << '\n';
        // ST st(fi);
        // vector<ll> ans(n, -1);
        // auto updd = [&](ll i, ll it, ll index) -> void {
        //     ans[index] = it;
        //     if (idx[i].size() > cur[i] + 1) {
        //         ++cur[i];
        //         st.upd(i, idx[i][cur[i]]);
        //     } else {
        //         st.upd(i, INF);
        //     }
        // };
        // updd(a[0], 0, 0);
        // ll ci = 0;
        // bool fl = false;
        // for (int it = 1; it < n; ++it) {
        //     if (ans[id] != -1) {
        //         return ans[id] + 1;
        //     }
        //     if (fl) {
        //         // cerr << ci + 1 << ' ' << it << '\n';
        //         updd(a[ci], it, ci + 1);
        //         ++ci;
        //         continue;
        //     }
        //     ll cidx = min(st.get(0, a[ci]), st.get(a[ci] + 1, n));
        //     cerr << cidx << '\n';
        //     if (cidx == INF) {
        //         fl = true;
        //         updd(a[ci], it, ci + 1);
        //         ++ci;
        //         continue;
        //     }
        //     updd(a[cidx], it, cidx);
        //     ci = cidx;
        // }
        // return ans[id] + 1;
        set<ll> st;
        for (int i = 0; i < n; ++i) st.insert(i);
        ll li = -1;
        vector<ll> ans(n, -1);
        bool fl = false;
        for (int it = 0; it < n; ++it) {
            cerr << fl << '\n';
            if (ans[id] != -1) {
                return ans[id];
            }
            if (li == -1 || fl) {
                ll idx = *st.begin();
                ans[idx] = it + 1;
                st.erase(st.begin());
                li = idx;
                continue;
            }
            ll nxt = INF;
            for (auto &i: st) {
                if (a[i] != a[li]) {
                    st.erase(i);
                    ans[i] = it + 1;
                    li = i;
                    nxt = i;
                    break;
                }
            }
            if (nxt == INF) {
                fl = true;
                ll idx = *st.begin();
                ans[idx] = it + 1;
                st.erase(st.begin());
                li = idx;
            }
        }
        return ans[id];
    };
    vector<ll> a(n);
    for (auto &i: a) cin >> i, --i;
    auto c = a;
    while (q--) {
        ll tp;
        cin >> tp;
        if (tp == 1) {
            ll idx;
            cin >> idx, --idx;
            swap(c[idx], c[idx + 1]);
        } else {
            ll idx;
            cin >> idx, --idx;
            cout << get(c, idx) << '\n';
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    solve();
}
