#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;
const int MAXN = 1e5 + 1;

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;
int ans[MAXN];
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 jj = 0;
                for (int ii = i; ii <= n; ++ii) {
                    while (used[jj]) {
                        jj++;
                    }
                    ans[jj] = ii;
                    used[jj] = 1;
                }

                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;
    }

    if (n <= 500 && q <= 500) {
        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';
            }
        }
        return 0;
    }

    rebuild();
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            if (a[x - 1] != a[x]) {
                swap(ans[x - 1], ans[x]);
            }
        }
        else {
            cout << ans[x - 1] << '\n';
        }
    }

}

/*
6 4
1 2 1 2 22
*/
