#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll

struct Fwk {
    int n;
    vector<int> t;

    Fwk(int n) : n(n) {
        t.resize(n + 1);
    }

    void add(int i, int x) {
        for (int j = i; j <= n; j += j & -j) {
            t[j] += x;
        }
    }

    int get(int r) {
        int s = 0;
        for (int j = r; j > 0; j -= j & -j) {
            s += t[j];
        }
        return s;
    }
};

int find(Fwk &a, Fwk &b) {
    int i = 0, n = a.n;
    // int l = 0, r = n + 1;
    // while (l + 1 < r) {
    //     int m = (l + r) / 2;
    //     if (a.get(m) - b.get(m) > 0) {
    //         r = m;
    //     } else {
    //         l = m;
    //     }
    // }
    // return r;
    const int Q = 14;
    for (int j = Q - 1; j >= 0; j--) {
        int nx = i + (1 << j);
        if (nx > n) {
            continue;
        }
        int sum = a.t[nx] - b.t[nx];
        if (sum == 0) {
            i = nx;
        }
    }
    return i + 1;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int mxa = *max_element(a.begin(), a.end());

    const int mv = (9 * n + 9) / 10;


    int t, x;
    if (mxa <= 2) {
        vector<Fwk> fw(mxa + 1, n);
        for (int i = 1; i <= n; i++) {
            fw[a[i]].add(i, 1);
        }
        for (int ts = 1; ts <= q; ts++) {
            cin >> t >> x;
            if (t == 1) {
                fw[a[x]].add(x, -1);
                fw[a[x + 1]].add(x + 1, -1);
                swap(a[x], a[x + 1]);
                fw[a[x]].add(x, 1);
                fw[a[x + 1]].add(x + 1, 1);
            } else {
                int v1 = a[x];
                int v2 = 3 - a[x];
                if (a[x] == a[1]) {
                    int pos = fw[v1].get(x);
                    int dop = min(pos - 1, fw[v2].get(n));
                    cout << pos + dop << "\n";
                } else {
                    int pos = fw[v1].get(x);
                    int dop = min(pos, fw[v2].get(n));
                    cout << pos + dop << "\n";
                }
            }
        }
        return;
    }
    vector<Fwk> fw(mxa + 1, n + 1);
    vector<int> used;
    Fwk all = n;
    for (int i = 1; i <= n; i++) {
        all.add(i, 1);
        fw[a[i]].add(i, 1);
    }
    for (int ts = 1; ts <= q; ts++) {
        cin >> t >> x;
        if (t == 1) {
            fw[a[x]].add(x, -1);
            fw[a[x + 1]].add(x + 1, -1);
            swap(a[x], a[x + 1]);
            fw[a[x]].add(x, 1);
            fw[a[x + 1]].add(x + 1, 1);
        } else {
            used.clear();
            int last = 0;
            for (int ord = 1; ord <= n; ord++) {
                int pos = find(all, fw[last]);
                if (pos > n) {
                    pos = find(all, fw[0]);
                }
                last = a[pos];
                all.add(pos, -1);
                fw[last].add(pos, -1);
                used.emplace_back(pos);
                if (pos == x) {
                    cout << ord << "\n";
                    break;
                }
            }
            for (auto j: used) {
                all.add(j, 1);
                fw[a[j]].add(j, 1);
            }
        }
    }
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    for (int ts = 1; ts <= t; ts++) {
        solve();
    }
}
