#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt")

using namespace std;
#define int long long int
#define fr(i, a, b) for(int i = (a); i <= (b); i++)
#define rf(i, a, b) for(int i = (a); i >= (b); i--)
#define fe(c, a) for (auto& c : a)
#define mk(a, b) make_pair((a), (b))
template<typename T>
using v = vector<T>;
using vi = v<int>;
using vvi = v<vi>;
using ii = pair<int, int>;
using vii = v<ii>;
using vvii = v<vii>; 

void solve() {
    int n; cin >> n;
    int q; cin >> q;
    vi a(n); fe(c, a) cin >> c;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int i; cin >> i; i--;
            swap(a[i], a[i+1]);
        }
        if (t == 2) {
            int x; cin >> x; x--;
            if (x == 0) {
                cout << 1 << '\n';
                continue;
            }
            vvi inds(n+1);
            set<ii> s;
            vi k(n+1, 0);
            fr(i, 0, n-1) inds[a[i]].push_back(i);
            fr(i, 0, n) if (!inds[i].empty()) s.insert({inds[i][0], i});
            int px = s.begin()->second;
            s.erase(s.begin());
            if (inds[px].size() > 1) s.insert(mk(inds[px][1], px));
            k[px]++;
            fr(i, 1, n-1) {
                auto j = s.begin();
                if (s.size() > 1 && px == s.begin()->second) {
                    j = next(j);
                }
                auto [ind, y] = *j;
                if (ind == x) {
                    cout << i+1 << '\n';
                    break;
                }
                px = y;
                k[y]++;
                s.erase(j);
                if (k[y] < inds[y].size()) s.insert(mk(inds[y][k[y]], y));
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int t = 1; 
    // cin >> t;
    while (t--)
        solve();
}