#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#pragma GCC optimize('O3')
#define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define int long long

signed main() {
    int n, q;
    cin >> n >> q;
    vector<int> o(n);
    vector<vector<int> > p(n);
    set<pair<int, int> > st;
    vector<bool> l;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        o[i] = x;
        o[i]--;
    }
/*
    10 2
    3 1 1 2 2 1 1 2 2 2
    1 1
    2 10
 */

    p.clear();
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[o[i]].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        reverse(p[i].begin(), p[i].end());
    }
    st.clear();
    vector<int> ll(n, 1);
    for (int i = 0; i < n; i++) {
        if (p[i].size()) {
            st.insert({p[i].back(), i});
            p[i].pop_back();
        }
    }
   vector<int>ans1(n);
    ans1[0] = 1;
    int last = 0;
    int col = 1;
    st.erase({last, o[last]});
    if (p[o[last]].size()) {
        st.insert({p[o[last]].back(), o[last]});
        p[o[last]].pop_back();
    }
    for (int i = 0;i < n - 1;i++){
        col++;
        if (st.begin()->second == o[last] && st.size() == 1) {
            last = st.begin()->first;
        } else {
            if (st.begin()->second == o[last]) {
                auto it = st.begin();
                it++;
                last = it->first;
            } else {
                last = st.begin()->first;
            }
        }
        st.erase({last, o[last]});
        if (!p[o[last]].empty()) {
            st.insert({p[o[last]].back(), o[last]});
            p[o[last]].pop_back();
        }
        ans1[last] = col;

        // cout << last << " ";
    }
    // cout << endl;
    swap(o[(9 * n + 9) / 10 - 1], o[(9 * n + 9) / 10]);
    p.clear();
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[o[i]].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        reverse(p[i].begin(), p[i].end());
    }
    st.clear();
    for (int i = 0; i < n; i++) {
        if (p[i].size()) {
            st.insert({p[i].back(), i});
            p[i].pop_back();
        }
    }
    vector<int>ans2(n);
    ans2[0] = 1;
    last = 0;
    col = 1;
    st.erase({last, o[last]});
    if (p[o[last]].size()) {
        st.insert({p[o[last]].back(), o[last]});
        p[o[last]].pop_back();
    }
    for (int i = 0;i < n - 1;i++){
        col++;
        if (st.begin()->second == o[last] && st.size() == 1) {
            last = st.begin()->first;
        } else {
            if (st.begin()->second == o[last]) {
                auto it = st.begin();
                it++;
                last = it->first;
            } else {
                last = st.begin()->first;
            }
        }
        st.erase({last, o[last]});
        if (!p[o[last]].empty()) {
            st.insert({p[o[last]].back(), o[last]});
            p[o[last]].pop_back();
        }
        ans2[last] = col;

        // cout << last << " ";
    }
    int m = 0;
    for (int i = 0;i < q;i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int y;
            cin >> y;
            m++;
        }else {
            int x;
            cin >> x;
            x--;
            if (m % 2 == 1)cout << ans1[x] << endl;
            else {
                cout << ans2[x] << endl;
            }
        }
    }
}
