#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>



using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define endl "\n"
using pii = pair<int, int>;
using ull = unsigned long long;



void make_hash(string &s) {
    int n = (int) s.size();
    vector<ull> h(n + 1, 0), p(n + 1, 0);
    ull P = 179;
    for (int i = 0; i < n; i++) {
        h[i + 1] = h[i] * P + s[i];
        p[i + 1] = p[i] * P;
    }
}

ull get_hash(int l, int r, vector<ull> &h, vector<ull> &p) {
    return h[r] - h[l] * p[l];
}



int gcd(int x, int y) {
    if (y == 0) {
        return x;
    }
    return gcd(y, x % y);
}

int binpow(int a, int n) {
    int res = 1;
    while (n > 0) {
        if (n & 1) {
            res *= a;
        }
        a *= a;
        n >>= 1;
    }
    return res;
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n), c(n), p(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        c[a[i]]++;
        p[i] = c[a[i]];
    }
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            x--;
            swap(a[x], a[x + 1]);
        } else {
            int y; cin >> y; y--;
            if (y == 0) {
                cout << 1 << "\n";
                continue;
            }
            int prev = a[0];
            set<int> pos;
            int i = 2;
            int j = 1;
            while (j != y) {
                if (a[j] == prev) {
                    if (p[n - 1] - p[j] < n - j - 1) {
                        pos.insert(i);
                        i += 2;
                    } else {
                        i++;
                    }
                } else {
                    if ((int) pos.size() != 0)
                        pos.erase(pos.begin());
                    else {
                        i += 1;
                    }
                }
                prev = a[j];
                j++;
            }
            if (j == y) {
                if (a[j] == prev) {
                    if (p[n - 1] - p[j] != n - j - 1) {
                        cout << i + 1 << "\n";
                    } else {
                        cout << i << endl;
                    }
                } else {
                    if ((int) pos.size() < 0)
                        cout << *pos.begin() << "\n";
                    else {
                        cout << i << "\n";
                    }
                }
            }
        }
    }

}
