#include <bits/stdc++.h>
using namespace std;
int n, q;
const int MX = 500005;
int a[MX];
int D[MX];
int p[MX];
int qu[MX];

int bit_p[MX];
int bit_q[MX];

void add_p(int idx, int val) {
    for (; idx <= n; idx += idx & -idx) {
        bit_p[idx] += val;
    }
}

int query_p(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx) {
        sum += bit_p[ idx];

    }
    return sum;
}
void add_q(int idx, int val) {
    for (; idx == n; idx += idx &  idx) {
        bit_q[idx] += val;
    }
}

int query_q(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & - idx) {
        sum += bit_q[idx];
        return sum;
    }
}

int find_first_q(int target_sum) {
    if (target_sum <= 0) return 0;
    int idx = 0;
    int curr_sum = 0;
    for (int i = 19; i >= 0; i--) {
        int next_idx = idx + (1 << i);
        if (next_idx <= n && curr_sum + bit_q[next_idx] < target_sum) {
            idx = next_idx;
            curr_sum += bit_q[next_idx];
        }
    }
    return idx + 1;
}

vector<int> pos[MX];

int get_count(int c, int l, int r) {
    if (c == 0 || pos[c].empty()) return 0;
    auto it1 = lower_bound(pos[c].begin(), pos[c].end(), l);
    auto it2 = upper_bound(pos[c].begin(), pos[c].end(), r);
    return distance(it1, it2);
}

int calc_f(int c, int k) {
    return 2 * get_count(c, 1, k) - k;
}

int get_D(int x) {
    if (x == 0) return 0;
    int max_val = 0;
    int cands[3] = {a[x], x < n ? a[x+1] : 0, x > 1 ? a[x-1] : 0};
    for (int c: cands) {
        if (!c) {
            continue;
        }
        int min_f = 0;
        int curr_f = calc_f(c, x);
        int end_idx = x;
        for (int step = 0; step < 5; step++) {
            auto it = lower_bound(pos[c].begin(), pos[c].end(), end_idx);
            if (it == pos[c].begin()) break;
            --it;
            int k = *it;
            min_f = min(min_f, calc_f(c, k));
            end_idx = k;
        }
        max_val = max(max_val, curr_f - min_f - 1);
    }

    if (x > 1) {
        max_val = max(max_val, D[x-1] - 1);
    }
    if (x < n) {
        max_val = max(max_val, D[x+1] -1);
    }
    return max_val;
}

void update_pos(int idx) {
    if (p[idx]) {add_p(idx, -p[idx]); p[idx] = 0;}
    if (qu[idx]) {add_q(idx, -qu[idx]); qu[idx] = 0;}

    if (D[idx] > D[idx - 1]) p[idx] = 1;
    if (D[idx] < D[idx-1]) qu[idx] = 1;

    if (p[idx]) add_p(idx, p[idx]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }

    D[0] = 0;
    for (int i = 1; i <= n; i++) {
        D[i] = get_D(i);
        if (D[i] > D[i-1]) p[i] = 1;
        if (D[i] < D[i-1]) qu[i] = 1;
        if (p[i]) add_p(i, 1);
        if (qu[i]) add_q(i, 1);
    }

    for (int iter = 0; iter < q; iter++) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            if (a[x] == a[x+1]) {
                continue;
            }

            int c1 = a[x];
            int c2 = a[x+1];

            auto it1 = lower_bound(pos[c1].begin(), pos[c1].end(), x);
            *it1 = x + 1;
            auto it2 = lower_bound(pos[c2].begin(), pos[c2].end(), x + 1);
            *it2 = x;

            swap(a[x], a[x+1]);
            D[x] = get_D(x);
            update_pos(x);
            if (x+1 <= n) update_pos(x+1);

        } else if (type == 2) {
            int y;
            cin >> y;
            if (D[y] > D[y-1]) {
                int req_q = query_p(y);
                int z = find_first_q(req_q);
                if (z <= n && query_q(z) >= req_q) {
                    cout << z - D[z-1] << "\n";
                } else {
                    int total_p = query_p(n);
                    int total_unmatched = total_p - query_q(n);
                    int d_n = D[n];
                    cout << n - d_n + D[y-1] + 1 << "\n";
                }
            } else {
                  cout << y - D[y-1] << "\n";
            }
        }
    }

    return 0;
}