#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define debug(x) cout << "\n!debug " << (#x) << ": " << x << "\n";
#define pii pair<int, int>

using ll = long long;
using ld = long double;

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v) {
    for (auto &e : v) out << e << ' ';
    return out;
}


void compress(int n, vector<int> &a) {
    vector<int> b = a;
    sort(all(b));
    unordered_map<int, int> codes;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (i == 0 || b[i] != b[i-1]) {
            codes[b[i]] = cnt;
            cnt++;
        }
    }

    for (auto &e : a) {
        e = codes[e];
    }
}

vector<int> nearest_right(int n, vector<int> &a) {
    vector<int> nearest(n, -1);
    vector<pii> blocks;
    // {num, size}
    blocks.emplace_back(a[0], 1);
    blocks.reserve(n);

    for (int i = 1; i < n; ++i) {
        pii last = blocks.back();
        if (last.first == a[i]) {
            blocks.pop_back();
            blocks.emplace_back(a[i], last.second+1);
        } else {
            blocks.emplace_back(a[i], 1);
        }
    }

    int j = 0;
    for (int i = 0; i < blocks.size(); ++i) {
        pii current = blocks[i];

        if (i == blocks.size()-1) {
            for (int e = j; e < j + current.second; ++e) {
                nearest[e] = -1;
            }
        } else {
            for (int e = j; e < j + current.second; ++e) {
                nearest[e] = j + current.second;
            }
        }

        j += current.second;
    }

    return nearest;
}

void find_x(int n, vector<int> &a, int pos) {
    vector<int> near = nearest_right(n, a);
    vector<int> posx(n, -1);

    int i = 0;
    int cnt = 1;
    int go_back = -1;
    while (i < n) {
        if (posx[i] != -1) {
            ++i; continue;
        }
        if (go_back != -1) {
            posx[i] = cnt;
            cnt++;
            i = go_back;
            go_back = -1;
            continue;
        }

        int next = near[i];
        if (next == -1) {
            posx[i] = cnt;
            ++i; ++cnt;
        } else if (next-i == 1) {
            posx[i] = cnt;
            ++i; ++cnt;
        } else {
            go_back = i+1;
            posx[i] = cnt;
            ++cnt;
            i = next;
        }
    }

    // debug(posx);
    cout << posx[pos] << '\n';
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    int colours_cnt = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // compress(n, a); // nlogn
    // debug(a);

    // vector<int> near = nearest_right(n, a);
    // debug(near);

    // find_x(n, a);

    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            swap(a[x-1], a[x]);
        } else {
            // Find x-th element
            find_x(n, a, x-1);
        }
    }
}