#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
typedef long double ld;
#define int long long
#define pii pair<int, int>
#define F first
#define S second

const int inf = 1e9;

vector<int> tr, a;

void build(int ind, int l, int r) {
    if (r - l == 1) {
        tr[ind] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * ind, l, mid);
    build(2 * ind + 1, mid, r);
    tr[ind] = min(tr[2 * ind], tr[2 * ind + 1]);
}

int get(int ind, int l, int r, int lq, int rq) {
    if (lq <= l && r <= rq) {
        return tr[ind];
    }
    if (lq >= r || rq <= l) {
        return inf;
    }
    int mid = (l + r) / 2;
    return min(get(2 * ind, l, mid, lq, rq), get(2 * ind + 1, mid, r, lq, rq));
}

void upd(int ind, int l, int r, int pos, int x) {
    if (r - l == 1) {
        tr[ind] = x;
        return;
    }
    int mid = (l + r) / 2;
    if (pos < mid) {
        upd(2 * ind, l, mid, pos, x);
    } else {
        upd(2 * ind + 1, mid, r, pos, x);
    }
    tr[ind] = min(tr[2 * ind], tr[2 * ind + 1]);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    a.clear();
    a.resize(5 * n);
    tr.clear();
    tr.resize(5 * n);
    vector<queue<int>> col;
    col.clear();
    col.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        col[arr[i]].push(i);
    }
    for (int i = 0; i <= n; i++) {
        col[i].push(inf);
    }
    for (int i = 0; i <= n; i++) {
        a[i] = col[i].front();
    }
    vector<int> t, t_col;
    t.clear();
    t.resize(n + 1, -1);
    t_col.clear();
    t_col.resize(n + 1);
    build(1, 0, n + 1);
    vector<int> t1(n + 1, -1);
    vector<int> t_col1(n + 1);
    int tc = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt = i;
        int tec = get(1, 0, n + 1, tc, tc + 1);
        upd(1, 0, n + 1, tc, inf);
        int ans = tr[1];
        upd(1, 0, n + 1, tc, tec);
        if (ans == inf) {
            break;
        }
        t_col[ans] = tc;
        tc = arr[ans];
        t[ans] = i - 1;
        col[tc].pop();
        upd(1, 0, n + 1, tc, col[tc].front());
    }
    cnt--;
    for (int i = 1; i <= n; i++) {
        if (t[i] == -1) {
            t_col[i] = tc;
            t[i] = cnt;
            cnt++;
        }
    }
    for (int i = 0; i < q; i++) {
        int ty, xi;
        cin >> ty >> xi;
        if (ty == 2) {
            cout << t[xi] + 1 << '\n';
        } else {
            if (arr[xi] != arr[xi + 1]) {
                swap(arr[xi], arr[xi + 1]);
                if (t[xi] > t[xi + 1]) {
                    swap(t[xi], t[xi + 1]);
                    swap(t_col[xi], t_col[xi + 1]);
                } else {
                    a.clear();
                    a.resize(5 * n);
                    tr.clear();
                    tr.resize(5 * n);
                    col.clear();
                    col.resize(n + 1);
                    for (int i = 1; i <= n; i++) {
                        col[arr[i]].push(i);
                    }
                    for (int i = 0; i <= n; i++) {
                        col[i].push(inf);
                    }
                    for (int i = 0; i <= n; i++) {
                        a[i] = col[i].front();
                    }
                    build(1, 0, n + 1);
                    t.clear();
                    t.resize(n + 1, -1);
                    t_col.clear();
                    t_col.resize(n + 1);
                    tc = 0, cnt = 0;
                    for (int i = 1; i <= n; i++) {
                        cnt = i;
                        int tec = get(1, 0, n + 1, tc, tc + 1);
                        upd(1, 0, n + 1, tc, inf);
                        int ans = tr[1];
                        upd(1, 0, n + 1, tc, tec);
                        if (ans == inf) {
                            break;
                        }
                        t_col[ans] = tc;
                        tc = arr[ans];
                        t[ans] = i - 1;
                        col[tc].pop();
                        upd(1, 0, n + 1, tc, col[tc].front());
                    }
                    cnt--;
                    for (int i = 1; i <= n; i++) {
                        if (t[i] == -1) {
                            t_col[i] = tc;
                            t[i] = cnt;
                            cnt++;
                        }
                    }
                }
            }
        }
    }
    return 0;
} 