// #pragma GCC optimize("Ofast")

#include <iostream>
#include <bits/stdc++.h>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define all(x) x.begin(), x.end()

#ifdef DEBUG
    #define debug(x) {cout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << "\n";};
    #define debugw(x) {cout << __func__ << ":" << __LINE__ << " " << x << "\n";};
#else
    #define debug(x)
    #define debugw(x)
#endif

int n, q;
vector<int> c;

vector<int> calc(vector<int> &c) {
    vector<int> res(n, -1);
    int last = -1;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int jk = n;
        for (int j = 0; j < n; j++) {
            if (res[j] == -1 && c[j] != last) {
                jk = j;
                break;
            }
        }

        if (jk == n) {
            break;
        }
        res[jk] = cnt++;
        last = c[jk];
    }

    for (int i = 0; i < n; i++) {
        if (res[i] == -1) {
            res[i] = cnt++;
        }
    }
    return res;
}

struct Nd {
    int color;
    vector<int> ind;
};

vector<int> calc2(vector<int> &c) {
    vector<int> res(n);

    vector<Nd> st;
    int last = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (c[i] != last) {
            st.push_back({c[i], {i}});
        } else {
            st.back().ind.push_back(i);
        }
        last = c[i];
    } 

    int cnt = 0;

    last = -1;
    while (st.size() > 1) {
        auto &nw = st[st.size() - 1];
        auto &ol = st[st.size() - 2];

        if (nw.color == ol.color) {
            for (auto &i: nw.ind) {
                ol.ind.push_back(i);
            }
            st.pop_back();
            continue;
        }

        if (last == nw.color) {
            res[ol.ind.back()] = cnt++;
            ol.ind.pop_back();

            last = ol.color;

            if (ol.ind.size() == 0) {
                // swap(nw, ol);
                swap(st[st.size() - 1], st[st.size() - 2]);
                st.pop_back();
            }


        } else {
            res[nw.ind.back()] = cnt++;
            nw.ind.pop_back();

            last = nw.color;

            if (nw.ind.size() == 0) {
                st.pop_back();
            }
        }
    }

    if (st.size()) {
        while (st[0].ind.size()) {
            res[st[0].ind.back()] = cnt++;
            st[0].ind.pop_back();
        }
    }

    return res;
}

bool check(vector<int> c, vector<int> c2) {
    for (int i = 0; i < c.size(); i++) {
        if (c[i] != c2[i]) {
            return false;
        }
    }
    return true;
}

void solve() {
    cin >> n >> q;
    c.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    vector<int> order = calc2(c);

    // assert(check(calc(c), calc2(c)));

    #ifdef DEBUG
        for (auto &i: order) {
            cout << i << " ";
        }
        cout << "\n";
    #endif

    // return;

    bool fl = true;
    for (int i = 0; i < q; i++) {
        int type, j;
        cin >> type >> j;
        j--;
        if (type == 1) {
            if (c[j] == 1 || c[j + 1] == 1) {
                swap(c[j], c[j + 1]);
            }
            // if (j == 0) {
            //     j += 2;
            // }
            // while (j < n - 1 && c[j] != c[j + 1]) {
            //     swap(order[j], order[j + 1]);
            //     j += 2;
            // }
            fl = false;
        } else {
            if (!fl) {
                // order = calc2(c);
                fl = true;
            }
            cout << order[j] + 1 << "\n";
        }

        // assert(check(order, calc2(c)));
    }
}

signed main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // cout << set_precision(8) << fixed;

    // ll T;
    // cin >> T;
    // while (T--) solve();

    solve();
}