#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = int;
using str = string;
using hashmap = gp_hash_table<ll,ll>;
using hashset = gp_hash_table<ll, null_type>;
using ordset = tree<ll,null_type, less<>,rb_tree_tag, tree_order_statistics_node_update>;

using pll = pair<ll,ll>;
auto SD = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(SD);
const ll mod = 998244353;


void sol() {
    ll n, q;cin>>n>>q;
    vector<ll> a(n);
    for (int i = 0; i <n ; i++) {
        cin>>a[i];
    }  priority_queue<ll> mn;
    vector<ll> ans;vector<deque<ll>> cc(n+1);
    for (int w =0 ; w< q; w++) {
        ll t;
        cin>>t;
        if (t==1) {
            ll xi;cin>>xi;
            swap(a[xi],a[xi-1]);
            ans.clear();
        } else {
            ll y;cin>>y;
            y--;
            if (y==0) {
                cout<<1<<endl;
            } else if (!ans.empty()){
                for (int i=0;i<n;i++) {
                    if (ans[i]==y) {
                        cout<<i+1<<'\n';
                        break;
                    }
                }
            } else {
                cc.assign(n+1,{});
                for (int i = 1;i <n ; i++) {
                    cc[a[i]].emplace_back(i);
                }

                for (int j = 1; j <= n;j++) {
                    if (!cc[j].empty()) {
                        mn.emplace(-(cc[j][0]));
                    }
                }
                ans.emplace_back(0);
                ll id = 1;
                while (!mn.empty()) {
                    if (ans.back()==y) {
                        id=ans.size();
                    }
                    auto r = mn.top();
                    mn.pop();
                    if (mn.empty()) {
                        for (auto Y: cc[a[-r]]) {
                            ans.emplace_back(Y);
                            if (ans.back()==y) {
                                id=ans.size();
                            }
                        }
                        break;
                    }else {
                        if (a[-r]==a[ans.back()]) {
                            auto r1 = mn.top();
                            ans.emplace_back(-r1);
                            mn.pop();
                            cc[a[-r1]].pop_front();
                            if (!cc[a[-r1]].empty()) {
                                mn.emplace(-cc[a[-r1]][0]);
                            }
                            mn.push(r);
                        }else {
                            ans.emplace_back(-r);
                            cc[a[-r]].pop_front();
                            if (!cc[a[-r]].empty()) {
                                mn.emplace(-cc[a[-r]][0]);
                            }
                        }
                    }
                }
                cout<<id<<endl;
            }
        }
     }
}
signed main() {
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cout<<fixed<<setprecision(19);
    ll t1 = 1;
    //cin>>t1
    while (t1--) {
        sol();
    }
}