#pragma GCC optimize("O3,unroll-loops")
#include<vector>
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#ifdef DBG
#define $(x) x
#else
#define $(x)
#endif

#define debug(x) $(cout << #x << " = " << x << endl)

#define all(x) x.begin(), x.end()

constexpr int INF = 1e9 + 7;
constexpr ll LINF = 1e18 + 7;

void WA() {
    cout << "THIS IS WRONG ANSWER" << endl;
    exit(0);
}

void RE() {
    exit(1);
}

void TL() {
    unsigned x = 0;
    while (true) x++;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
    }

    vector<int> tm(n, n);
    vector<int> pr(n, n);
    for (int i = n - 1; i >= 0; --i) {
        tm[i] = pr[a[i]];
        pr[a[i]] = i;
    }

    vector<bool> b(n, 0);
    for (int i = 0; i < n; ++i) {
        if (pr[i] != n) {
            b[pr[i]] = 1;
        }
    }

    int p1 = 0;
    int p2 = 0;

    vector<int> ps(n, -1);

    int ls = -1;
    vector<int> v, w;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) v.push_back(i);
        else w.push_back(i);
    }

    vector<int> tv(v.size()), tw(w.size());
    int vp = 0;
    int wp = 0;
    bool l = 0;
    int t = 0;
    while (vp < v.size() && wp < w.size()) {
        debug(vp << ' ' << wp);
        if (wp < w.size() && (l || (vp < v.size() && v[vp] > w[wp]))) {
            tw[wp++] = t++;
            l = 0;
        } else {
            tv[vp++] = t++;
            l = 1;
        }
    }

    while (vp < v.size()) {
        tv[vp++] = t++;
    }

    while (wp < w.size()) {
        tw[wp++] = t++;
    }


    for (int qq = 0; qq < q; ++qq) {
        int t, qi;
        cin >> t >> qi;
        qi--;
        if (t == 1) {
            if (a[qi] == a[qi + 1] || a[qi] == 0 && a[qi + 1] == 0) continue;
            swap(a[qi], a[qi + 1]);

            if (a[qi] == 0) {
                *find(all(b), qi) = qi + 1;
                *find(all(a), qi + 1) = qi;
            } else {
                *find(all(a), qi) = qi + 1;
                *find(all(b), qi + 1) = qi;
            }
        } else {
            if (a[qi] != 0) {
                cout << tw[lower_bound(all(w), qi) - w.begin()] + 1 << '\n';
            } else {
                cout << tv[lower_bound(all(v), qi) - v.begin()] + 1 << '\n';
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    $(cin >> t);
    while (t--) {
        debug("=-=-=-=-=-=-=-=");
        solve();
    }
}