#include <bits/stdc++.h>
#define int long long

#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")

using namespace std;
const int MOD = 998'244'353;
const int INF = 1e9 + 7;

int binpow(int x, int m) {
    if (m == 0)
        return 1;
    if (m == 1)
        return x;
    if (m % 2 == 0) {
        int res = binpow(x, m / 2);
        return (res * res) % MOD;
    }
    return (binpow(x, m - 1) * x) % MOD;
}

int n;
vector<int> a;
unordered_map<int, int> ans;
void rebuild() {
    vector<int> used(n);
    int last = 0;
    ans[last] = 1;
    used[last] = 1;

    for (int i = 2; i <= n; ++i) {
        int j = 0;
        while (a[j] == a[last] || used[j]) {
            j++;
            if (j == n) {
                int j = 0;
                for (int ii = i; ii <= n; ++ii) {
                    while (used[j]) {
                        j++;
                    }
                    ans[j] = ii;
                }
                return;
            }
        }
        last = j;
        ans[last] = i;
        used[last] = 1;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int q;
    cin >> n >> q;
    a.resize(n);
    for (auto &i : a) {
        cin >> i;
    }

    bool f = 1;
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            swap(a[x - 1], a[x]);
            f = 1;
        }
        else {
            if (f) {
                rebuild();
                /*
                cout << "---" << '\n';
                for (auto i : ans) {
                    cout << i.first << " " << i.second << '\n';
                }
                */
                f = 0;
            }
            cout << ans[x - 1] << '\n';
        }
    }

}

/*
int n, k;
cin >> n >> k;
vector<int> x(n), p(k);
for (auto &i : x)
    cin >> i;
for (auto &i : p)
    cin >> i;
*/
