#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<set>
#include<iomanip>
#include<random>
#include<chrono> 
using namespace std;
using ll = long long;
using ld = long double;

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx")

#define int long long
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;

int bin(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) {
            res = a * res % mod;
        }
        n /= 2;
        a = a * a % mod;
    }
    return res;
}

vector<vector<int>> g;
vector<int> sz;

void dfs(int v) {
    sz[v] = 1;
    for (auto to : g[v]) {
        dfs(to);
        sz[v] += sz[to];
    }
}

int goy(int x) {
    return (x % mod + mod) % mod;
}

vector<pii> t;

void build(int v, int l, int r, vector<int>& a) {
    if (r - l == 1) {
        t[v] = { a[l], l };
        return;
    }
    int m = (l + r) / 2;
    build(2 * v + 1, l, m, a);
    build(2 * v + 2, m, r, a);
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

void upd(int v, int l, int r, int pos, int val) {
    if (r - l == 1) {
        t[v] = { val, l };
        return;
    }
    int m = (l + r) / 2;
    if (pos < m) {
        upd(2 * v + 1, l, m, pos, val);
    }
    else {
        upd(2 * v + 2, m, r, pos, val);
    }
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

const int inf = 1e9 + 1;

pii get(int v, int l, int r, int ql, int qr) {
    if (qr <= l || r <= ql) return { inf, inf };
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) / 2;
    return min(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        v[i]--;
    }
    t.resize(4 * n);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int a;
            cin >> a;
            --a;
            swap(v[a], v[a + 1]);
        }
        else {
            vector<vector<int>> pos(n);
            for (int i = 0; i < n; ++i) {
                pos[v[i]].push_back(i);
            }
            for (int i = 0; i < n; ++i) {
                pos[i].push_back(inf);
                reverse(all(pos[i]));
            }
            vector<int> v1(n);
            for (int i = 0; i < n; ++i) {
                v1[i] = pos[i].back();
            }
            build(0, 0, n, v1);
            int id;
            cin >> id;
            if (id == 10) {
                int gg = 0;
            }
            int last = v[0];
            if (id == 1) {
                cout << 1 << '\n';
                continue;
            }
            pos[v[0]].pop_back();
            upd(0, 0, n, v[0], pos[v[0]].back());
            for (int i = 1; i < n; ++i) {
                pii p = min(get(0, 0, n, 0, last), get(0, 0, n, last + 1, n));
                if (p.first == inf) {
                    p = get(0, 0, n, 0, n);
                }
                if (pos[p.second].back() == id - 1) {
                    cout << i + 1 << '\n';
                    break;
                }
                last = p.second;
                pos[p.second].pop_back();
                upd(0, 0, n, p.second, pos[p.second].back());
            }
        }
    }
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
