#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using ll = long long;
using ld = long double;
mt19937 rnd(1245);

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const ll mod = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const int maxn = 1e5 + 1;
const int logn = 21;
const int sq = 350;
const ld eps = 1e-8;
const ld pi = acos(-1);

ll mmod(ll x, ll mod = mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

ll gcd(ll a, ll b) {
    ll res;
    while (b != 0) {
        res = a;
        a = b;
        b = res % a;
    }
    return a;
}

ll binpow(ll a, ll n, ll mod = mod) {
    ll res = 1;
    while (n != 0) {
        if (n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int t[maxn];

void build(int v, int l, int r, const vector<int>& a) {
    if (r - l == 1) {
        t[v] = a[l];
        return;
    }
    int mid = (r + l) / 2;
    build(2 * v + 1, l, mid, a);
    build(2 * v + 2, mid, r, a);
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

void upd(int v, int l, int r, int idx, int val) {
    if (r - l == 1) {
        t[v] = val;
        return;
    }
    int mid = (r + l) / 2;
    if (idx < mid) {
        upd(2 * v + 1, l, mid, idx, val);
    }
    else {
        upd(2 * v + 2, mid, r, idx, val);
    }
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

int get(int v, int l, int r, int ql, int qr) {
    if (r <= ql || l >= qr) {
        return inf;
    }
    if (l >= ql && r <= qr) {
        return t[v];
    }
    int mid = (r + l) / 2;
    return min(get(2 * v + 1, l, mid, ql, qr), get(2 * v + 2, mid, r, ql, qr));
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<set<int> > g(n + 1);
    vector<int> bl(n + 1, n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        g[a[i]].insert(i);
        if (bl[a[i]] == n + 1) bl[a[i]] = i;
    }
    for (int i = 1; i < n + 1; ++i) {
        g[i].insert(n + 1);
    }

    build(0, 0, n + 1, bl);
    vector<int> f(n, 0);
    while (q--) {
        int type, x;
        cin >> type >> x;
        if (type == 1) {
            if (a[x - 1] == a[x]) {
                continue;
            }
            g[a[x - 1]].erase(x - 1);
            g[a[x]].erase(x);
            g[a[x - 1]].insert(x);
            g[a[x]].insert(x - 1);
            swap(a[x], a[x - 1]);
        }
        else {
            int cnt = 1;
            int now = 0;
            int prev = 0;
            while (now != x - 1) {
                while (f[now] == 1) {
                    now++;
                }
                if (a[now] != prev) {
                    prev = a[now];
                    int idx1 = *upper_bound(all(g[a[now]]), now);
                    upd(0, 0, n + 1, a[now], idx1);
                    cnt++;
                    f[now] = 1;
                    now++;
                }
                else {
                    int idx = min(get(0, 0, n + 1, 1, a[now]), get(0, 0, n + 1, a[now] + 1, n + 1));
                    if (idx == n + 1) {
                        cnt++;
                        prev = a[now];
                        int idx1 = *upper_bound(all(g[a[now]]), now);
                        upd(0, 0, n + 1, a[now], idx1);
                        f[now] = 1;
                        now++;
                    }
                    else if (idx == x - 1) {
                        prev = a[now];
                        now = x - 1;
                        break;
                    }
                    else {
                        cnt += 2;
                        prev = a[now];
                        f[idx] = 1;
                        f[now] = 1;

                        int idx1 = *upper_bound(all(g[a[idx]]), idx);
                        upd(0, 0, n + 1, a[idx], idx1);
                        idx1 = *upper_bound(all(g[a[now]]), now);
                        upd(0, 0, n + 1, a[now], idx1);
                        now++;
                    }
                }
            }

            if (prev == a[now]) {
                int idx = min(get(0, 0, n + 1, 1, a[now]), get(0, 0, n + 1, a[now] + 1, n + 1));
                if (idx != n + 1) {
                    cnt++;
                }
            }

            cout << cnt << '\n';

            fill(all(f), 0);
        }

        fill(all(bl), n + 1);

        for (int i = 0; i < n; ++i) {
            if (bl[a[i]] == n + 1) bl[a[i]] = i;
        }

        build(0, 0, n + 1, bl);
    }


}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }

}