#include<bits/stdc++.h>
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
using ll = long long;
//using oset = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;


/*
struct segtree{
    vector<ll> tree;
    ll sz;
    ll def = 0;
    ll merg(ll a, ll b) {
        return a + b;
    }
    void clar(ll n) {
        tree.assign(4 * n, def);
        sz = n;
    }
    segtree() {

    }
    void build(ll v, ll l, ll r, vector<ll> & a) {
        if (r - l == 1) {
            tree[v] = a[l];
            return;
        }
        ll m = (l + r) / 2;
        build(v * 2 + 1, l, m, a);
        build(v * 2 + 2, m, r, a);
        tree[v] = merg(tree[v * 2 + 1], tree[v * 2 + 2]);
    }
    segtree(vector<ll> & a) {
        ll n = (ll)a.size();
        clar(n);
        build(0, 0, sz, a);
    }
};
*/

ll mod = 998244353;

ll po(ll x, ll n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        ll c = po(x, n / 2);
        return (c * c) % mod;
    } else {
        return (x * po(x, n - 1)) % mod;
    }
}

int n;

vector<int> vsp;

void get(vector<int> & a) {
    vector<vector<int>> pr(n);
    for (int i = 0; i < n; i++) {
        pr[a[i]].push_back(i);
    }
    vector<int> nac(n, -1);
    set<pair<int, int>> se;
    for (int i = 0; i < n; i++) {
        if (pr[i].size()) {
            nac[i] = pr[i][0];
            se.insert({nac[i], i});
        }
    }
    vector<int> it(n, 0);
    vsp[0] = 0;
    int pref = a[0];
    it[a[0]]++;
    if (pr[a[0]].size() == 1) {
        se.erase({0, a[0]});
        nac[a[0]] = -1;
    } else {
        se.erase({0, a[0]});
        nac[a[0]] = pr[a[0]][it[a[0]]];
        se.insert({nac[a[0]], a[0]});
    }
    for (int i = 1; i < n; i++) {
        if (se.size() == 1) {
            auto [a, j] = *se.begin();
            vsp[pr[j][it[j]]] = i;
            it[j]++;
            se.erase(se.begin());
            if (i != n - 1) {
                nac[j] = pr[j][it[j]];
                se.insert({pr[j][it[j]], j});
            }
        } else {
            if (nac[pref] != -1) {
                se.erase({nac[pref], pref});
            }
            auto [a, j] = *se.begin();
            vsp[pr[j][it[j]]] = i;
            it[j]++;
            se.erase(se.begin());
            if (it[j] != (int)pr[j].size()) {
                nac[j] = pr[j][it[j]];
                se.insert({nac[j], j});
            } else {
                nac[j] = -1;
            }
            if (nac[pref] != -1) {
                se.insert({nac[pref], pref});
            }
            pref = j;
        }
    }
}

void solve() {
    int q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto & i : a) {
        cin >> i;
        //i--;
        i = rand() % n;
    }
    vsp.resize(n);
    get(a);
    vector<ll> tip(q);
    vector<ll> num(q);
    for (ll i = 0; i < q; i++) {
        cin >> tip[i] >> num[i];
    }
    for (ll i = 0; i < q; i++) {
        ll t = tip[i];
        //cin >> t;
        //t = 1;
        if (t == 1) {
            ll x;
            //cin >> x;
            x = num[i];
            x--;
            if (a[x] != a[x + 1]) {
                swap(a[x], a[x + 1]);
                if (i + 1 < q && tip[i + 1] == 2) {
                    get(a);
                }
            }
        } else {
            ll v;
            v = num[i];
            //cin >> v;
            v--;
            cout << vsp[v] + 1 << '\n';
        }
    }
}

signed main() {
    int MULTITEST = 0;
    #ifdef zapvm
        MULTITEST = 1;
        freopen("in.txt", "r", stdin);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    if (MULTITEST) {
        cin >> t;
    }
    while (t--) {
        solve();
    }
}