#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 * 5 + 10;

int n, q;
int a[N];

vector<int> pos[N];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int _ = 0; _ < q; _++) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            x--;
            swap(a[x], a[x + 1]);
        } else {
            int y;
            cin >> y;
            y--;
            for (int i = 0; i < n; i++) pos[a[i]].emplace_back(i);
            int x, ans = 0, at = 0;
            for (int j = 0; j < (int) pos[a[y]].size(); j++)
                if (pos[a[y]][j] == y) {
                    at = j;
                    break;
                }
            x = at;
            while (x > 0 && pos[a[y]][x - 1] + 1 == pos[a[y]][x])
                x--;
            int higher = (int) pos[a[y]].size() - at - 1;
            at -= x;
            x = pos[a[y]][x];
            vector<int> cnt(n + 1, 0);
            for (int j = 0; j < x; j++) cnt[a[j]]++;
            int badX = -1;
            for (int j = 0; j <= n; j++)
                if (cnt[j] > x / 2)
                    badX = j;
            if (badX == -1) {
                ans = x + 1;
            } else {
                int v = pos[badX][0];
                if (badX != a[x]) {
                    int remain = x - v - cnt[badX];
                    ans = v + 2 * (remain + 1);
                } else {
                    ans = v + cnt[badX] * 2 + 2;
                }
            }
            if (ans + 2 * at > n) {
                cout << n - higher << "\n";
            } else {
                cout << min(n, ans + 2 * at) << "\n";
            }
            for (int i = 0; i <= n; i++) pos[i].clear();
        }
    }

    return 0;
}
