#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

vector<pair<ll, ll>> cnt_ans(vector<ll>& a, ll n) {
    vector<pair<ll, ll>> ex(n, {-1, -1});
    ll time = 1;
    set<ll> first;
    vector<vector<ll>> f(n + 1);
    vector<ll> ptr(n + 1), ban(n + 1);
    for (ll i = 0; i < n; i++) {
        if (f[a[i]].empty()) {
            first.emplace(i);
        }
        f[a[i]].push_back(i);
    }

    for (ll i = 0; i < n; i++) {
        if (ex[i] != pair{-1LL, -1LL}) continue;
        if (i > 0 && a[i] == a[i - 1] && time == ex[i - 1].first + 1) {
            auto it = first.begin();
            while (!first.empty() && *first.begin() <= i) {
                it = first.begin();
                while (ptr[a[*it]] < f[a[*it]].size() &&
                       ex[f[a[*it]][ptr[a[*it]]]] != pair{-1LL, -1LL}) {
                    ptr[a[*it]]++;
                }
                if (ptr[a[*it]] < f[a[*it]].size())
                    first.emplace(f[a[*it]][ptr[a[*it]]]);
                first.erase(*it);
            }
            it = first.begin();
            if (first.empty() || (first.size() == 1 && a[*it] == a[i]))
                goto fig;
            ll j = *it;
            while (a[*it] == a[i] || ban[a[*it]] == i) {
                it++;
                if (ban[a[j]] == i && ptr[a[*it]] < f[a[*it]].size() - 1 &&
                    f[a[j]][ptr[a[j]] + 1] < *it) {
                    j = f[a[j]][ptr[a[j]] + 1];
                    break;
                }
                j = *it;
            }

            // ban[a[j]] = i + 1;
            if (first.count(j) && ptr[a[j]] < f[a[j]].size() - 1) {
                ptr[a[j]]++;
                first.emplace(f[a[j]][ptr[a[j]]]);
            }
            first.erase(j);
            ex[j] = {time++, i};
        }
    fig:
        ex[i] = {time++, -1};
    }
    return ex;
}

void solve() {
    ll n, q, t, x;
    cin >> n >> q;
    vector<ll> a(n);
    for (ll& l : a) {
        cin >> l;
    }

    while (q--) {
        cin >> t >> x;
        switch (t) {
            case 1:
                swap(a[x - 1], a[x]);
                break;
            case 2:
                auto ex = cnt_ans(a, n);
                cout << ex[x - 1].first << '\n';
                break;
        }
    }

    cout << endl;
}

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

    ll t = 1;
#ifdef LOCAL
    freopen("in_a.txt", "r", stdin);
    cin >> t;
#endif

    while (t--) solve();
}