#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define all(a) a.begin(), a.end()

void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
#ifdef LOCAL
    cin >> t;
#else
#endif
    while (t--) solve();
}

const ll N = 5e5 + 10;
ll n, q;
ll fen[N];

void fadd(ll lx, ll rx, ll umn = 1) {
    if (umn == 1) {
        for (ll i = lx + 1; i < N; i += i & -i)
            fen[i] += lx;
        for (ll i = rx + 1; i < N; i += i & -i)
            fen[i] -= lx;
    } else {
        for (ll i = lx + 1; i < N; i += i & -i)
            fen[i] -= lx;
        for (ll i = rx + 1; i < N; i += i & -i)
            fen[i] += lx;
    }
}

ll getl(ll j) {
    ll res = 0;
    for (ll i = j + 1; j > 0; j -= j & -j) {
        res += fen[i];
    }
    return res;
}

void solve() {
    cin >> n >> q;
    fill(fen, fen + n + 10, 0);
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < q; i++) {
        ll t, x;
        cin >> t >> x;
        x--;
        if (t == 1)
            swap(a[x], a[x + 1]);
        else {
            ll bl = 0, c = a[0], cc = 0, cn = 0;
            for (ll i = 0; i < n; i++) {
                if (a[i] == c) cc++;
                else {
                    cn++;
                    if (cc == cn) {
                        bl += cc + cn - 1;
                        c = a[i];
                        cc = 1, cn = 0;
                    }
                }
                if (i == x) {
                    if (a[i] == c)
                        cout << min(n, bl + cc * 2 - 1) << "\n";
                    else
                        cout << min(n, bl + cn * 2) << "\n";
                }
            }
        }
    }
    return;
    vector<vector<ll> > f(n);
    vector<ll> rx(n);
    ll curc = -1, bal = -1, lx = -1;
    for (ll i = 0; i < n; i++) {
        f[a[i]].push_back(i);
        if (i == 0) {
            curc = a[i];
            lx = i;
            bal = 1;
        } else {
            if (a[i] == curc) bal++;
            else bal--;
            if (bal == 0) {
                rx[lx] = i;
                fadd(lx, i);
                curc = a[i], lx = i, bal = 1;
            }
        }
    }
    fadd(lx, n);
    a.push_back(-1);
    auto cnt = [&](ll c, ll l, ll r)-> ll {
        return lower_bound(all(f[c]), r) - lower_bound(all(f[c]), l);
    };
    auto cbl = [&](ll c, ll l, ll r)-> ll {
        return cnt(c, l, r) * 2 - (r - l);
    };
    for (ll z = 0; z < q; z++) {
        ll t, x;
        cin >> t >> x;
        x--;
        ll l = getl(x), r = rx[l], c = a[l];
        if (t == 2) {
            if (a[x] == c)
                cout << cnt(c, l, x) * 2 + 1 << "\n";
            else
                cout << ((x - l) - cnt(c, l, x) + 1) * 2 << "\n";
        } else {
            if (x + 1 < r) {
                if (a[x] == c && a[x + 1] != c && cbl(c, l, x + 1) == 1) {
                    fadd(l, r, -1);
                    rx[l] = x;
                    fadd(l, x);
                    rx[x] = x + 1;
                    fadd(x, l + 1);
                    rx[x + 1] = r;
                    fadd(x + 1, r);
                }
            } else if (a[l] == c && a[r] == c)
                swap(*lower_bound(all(f[a[x]]), x),
                     *lower_bound(all(f[a[x + 1]]), x + 1));
            swap(a[x], a[x + 1]);
        }
    }
}
