#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#define int long long
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define ll long long
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag,
//tree_order_statistics_node_update> ordered_set;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll_loops")
const ll inf = 1e9 + 10;
const ll mod = 998244353;
const ll maxn = 5e5 + 10;

//set<int> col[maxn];

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<set<int>> col(maxn);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        col[a[i]].insert(i);
    }

    //if ( n * q > 1000) {
    //    cout << -1;
    //    return;
   // }
    for (int j = 0; j < q; j++) {
        int t;
        cin >> t;
        //cout << t << "!" << endl;
        if (t == 1) {
            int x;
            cin >> x; x--;
            //cout << t << " " << x << endl;
            col[a[x]].erase(x); col[a[x]].insert(x + 1);
            col[a[x + 1]].erase(x + 1); col[a[x + 1]].insert(x);
            swap(a[x], a[x + 1]);
        }
        else {
            set<int> que;
            for (int i = 0; i < maxn; i++) {
                if (!col[i].empty())
                    que.insert(*col[i].begin());
            }

            int ind = 2;
            int y;
            cin >> y;
            y--;

            if (y == 0) {
                cout << 1 << "\n";
                continue;
            }
            int last = a[0];
            que.erase(0);
            vector<set<int>::iterator> it(n + 1);
            for (int i = 0; i < maxn; i++) {
                if (!col[i].empty())
                    it[i] = col[i].begin();
            }
            it[a[0]]++;
            if (it[a[0]] != col[a[0]].end()) {
                que.insert(*it[a[0]]);
                //it[a[0]]++;
            }
            int cnt = 100;
            while (true && cnt--) {
                if (it[last] != col[last].end() && sz(que) > 1)
                    que.erase(*it[last]);
                int cur = *que.begin();
                //cout << cur + 1 << "?" << endl;
                if (cur == y) {
                    cout << ind << "\n";
                    break;
                }
                que.erase(que.begin());
                if (it[last] != col[last].end() && a[cur] != last)
                    que.insert(*it[last]);
                it[a[cur]]++;
                if (it[a[cur]] != col[a[cur]].end())
                    que.insert(*it[a[cur]]);
                last = a[cur];
                ind++;
            }
        }
    }
}

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

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