#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

int sol(vector<int>&a, int y) {
    int n = sz(a);
    vector<int> ans(n, -1);
    int p1 = 0, p2 = 1;
    auto tryp = [&](int p, int vl) {
        return (p == 0 || ans[p - 1] != vl);
    };
    auto move = [&](int &p) {
        while (p <n  && ans[p] != -1) p++;
    };
    // for (auto u:a)cout<<u<<' ';
    // cout<<endl;
    int fm = -1;
    for (int j = n - 2; j >= 0; j--) {
        if (a[j] !=a[j +1]) {
            fm=j; break;
        }
    }
    int lp = -1;
    for (int j = 0; j <= y; j++) {
        // for(auto u : ans) cout << u << ' ';
        // cout << endl;
        // cout << p1 << ' ' << p2 << endl;
        if (p1 > p2)swap(p1, p2);
        if (j > fm) {
            ans[p1] = a[j];
            lp = p1; move(p1); continue;
        }
        if (tryp(p1,a[j])) {
            ans[p1] = a[j];
            lp = p1; move(p1);
        } else {
            while (p2< n && !tryp(p2,a[j])) p2++;
            ans[p2] = a[j];
            lp = p2;
            move(p2);
        }
        if (p1==p2) p2++;
    }
    // for(auto u : ans) cout << u << ' ';
    //     cout << endl;
    //     cout << p1 << ' ' << p2 << endl;
    return lp;
}

vector<int> kek(vector<int> a){
    vector<int>ans(sz(a));
    for (int j = 0; j < sz(a);j ++) ans[a[j] - 1] = j;
    return ans;
}

void solve() {
    int n,q ; cin >>n >> q;
    vector<int> a(n);
    for(auto&u:a) cin >> u;
    
    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--;
            cout << sol(a, y) + 1 << '\n';
        }
        // for (auto &u : sol(a)) cout << u << ' ';
        // cout<< endl;
    }
}

signed main() {
    int t = 1;
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> t;
    #else 
        cin.tie(0)->sync_with_stdio(false);
    #endif 

    while (t--) solve();

    return 0;
}