#include <iostream>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int a[n];
    bool tw = true;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] > 2) {
            tw = false;
        }
    }
    if (tw) {
        int pos[n], ord[n];
        ord[0] = 0;
        pos[0] = 0;
        queue <int> qu;
        int p = 1, t = 1;
        while (t < n) {
            if (p == n) {
                pos[qu.front()] = t;
                ord[t] = qu.front();
                qu.pop();
                ++t;
            } else if (qu.empty()) {
                if (a[p] == a[ord[t - 1]]) {
                    qu.push(p);
                    ++p;
                } else {
                    pos[p] = t;
                    ord[t] = p;
                    ++t;
                    ++p;
                }
            } else if (a[ord[t - 1]] == a[qu.front()]) {
                if (a[p] == a[ord[t - 1]]) {
                    qu.push(p);
                    ++p;
                } else {
                    pos[p] = t;
                    ord[t] = p;
                    ++t;
                    ++p;
                }
            } else {
                pos[qu.front()] = t;
                ord[t] = qu.front();
                qu.pop();
                ++t;
            }
        }
        for (int w = 0; w < q; ++w) {
            cin >> t >> p;
            if (t == 2) {
                cout << pos[p - 1] + 1 << "\n";
            } else {
                --p;
                if (a[p] == a[p + 1]) {
                    continue;
                }
                swap(pos[p], pos[p + 1]);
                swap(a[p], a[p + 1]);
            }
        }
    } else {
        for (int i = 0; i < n; ++i) {
            if (a[i] != 1) {
                a[i] = 2;
            }
        }
        int pos[n], ord[n];
        ord[0] = 0;
        pos[0] = 0;
        queue <int> qu;
        int p = 1, t = 1;
        while (t < n) {
            if (p == n) {
                pos[qu.front()] = t;
                ord[t] = qu.front();
                qu.pop();
                ++t;
            } else if (qu.empty()) {
                if (a[p] == a[ord[t - 1]]) {
                    qu.push(p);
                    ++p;
                } else {
                    pos[p] = t;
                    ord[t] = p;
                    ++t;
                    ++p;
                }
            } else if (a[ord[t - 1]] == a[qu.front()]) {
                if (a[p] == a[ord[t - 1]]) {
                    qu.push(p);
                    ++p;
                } else {
                    pos[p] = t;
                    ord[t] = p;
                    ++t;
                    ++p;
                }
            } else {
                pos[qu.front()] = t;
                ord[t] = qu.front();
                qu.pop();
                ++t;
            }
        }
        for (int w = 0; w < q; ++w) {
            cin >> t >> p;
            if (t == 2) {
                cout << pos[p - 1] + 1 << "\n";
            } else {
                --p;
                if (a[p] == a[p + 1]) {
                    continue;
                }
                swap(pos[p], pos[p + 1]);
                swap(a[p], a[p + 1]);
            }
        }
        /*int pos[n], ord[n];
        ord[0] = 0;
        pos[0] = 0;
        queue <int> qu;
        int p = 1, t = 1;
        while (t < n) {
            if (p == n) {
                pos[qu.front()] = t;
                ord[t] = qu.front();
                qu.pop();
                ++t;
            } else if (qu.empty()) {
                if (a[p] == a[ord[t - 1]]) {
                    qu.push(p);
                    ++p;
                } else {
                    pos[p] = t;
                    ord[t] = p;
                    ++t;
                    ++p;
                }
            } else if (a[ord[t - 1]] == a[qu.front()]) {
                if (a[p] == a[ord[t - 1]]) {
                    qu.push(p);
                    ++p;
                } else {
                    pos[p] = t;
                    ord[t] = p;
                    ++t;
                    ++p;
                }
            } else {
                pos[qu.front()] = t;
                ord[t] = qu.front();
                qu.pop();
                ++t;
            }
        }
        for (int w = 0; w < q; ++w) {
            cin >> t >> p;
            if (t == 2) {
                cout << pos[p - 1] + 1 << "\n";
            } else {
                --p;
                if (a[p] == a[p + 1]) {
                    continue;
                }
                //if (p == 0) {
                //    swap(a[0], a[1]);
                //    continue;
                //}
                if (a[p + 1] == a[ord[pos[p] - 1]]) {
                    swap(a[p], a[p + 1]);
                    continue;
                }
                swap(a[p], a[p + 1]);
                ord[0] = 0;
                pos[0] = 0;
                while (!qu.empty()) {
                    qu.pop();
                }
                p = 1;
                t = 1;
                while (t < n) {
                    if (p == n) {
                        pos[qu.front()] = t;
                        ord[t] = qu.front();
                        qu.pop();
                        ++t;
                    } else if (qu.empty()) {
                        if (a[p] == a[ord[t - 1]]) {
                            qu.push(p);
                            ++p;
                        } else {
                            pos[p] = t;
                            ord[t] = p;
                            ++t;
                            ++p;
                        }
                    } else if (a[ord[t - 1]] == a[qu.front()]) {
                        if (a[p] == a[ord[t - 1]]) {
                            qu.push(p);
                            ++p;
                        } else {
                            pos[p] = t;
                            ord[t] = p;
                            ++t;
                            ++p;
                        }
                    } else {
                        pos[qu.front()] = t;
                        ord[t] = qu.front();
                        qu.pop();
                        ++t;
                    }
                }
            }
        }*/
    }
    return 0;
}
