#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9+7;

struct D_O {
    vector<int>tree, a;

    void build(int i, int l, int r) {
        if (r-l == 1) tree[i] = a[l];
        else {
            int m = (r+l)/2;
            build(i*2+1, l, m);
            build(i*2+2, m, r);
            tree[i] = min(tree[i*2+1], tree[i*2+2]);
        }
    }

    D_O() {}

    D_O(vector<int>&a1) {
        tree.resize(a1.size()*4);
        a.resize(a1.size()); for (int i = 0; i < a1.size(); i++) a[i] = a1[i];
        build(0, 0, a1.size());
    }

    void update(int i, int l, int r, int ind, int x) {
        if (r-l == 1) tree[i] = x;
        else {
            int m = (r+l)/2;
            if (m > ind) update(i*2+1, l, m, ind, x);
            else update(i*2+2, m, r, ind, x);
            tree[i] = min(tree[i*2+1], tree[i*2+2]);
        }
    }

    int get(int i, int l, int r, int lq, int rq) {
        if (l >= lq && r <= rq) return tree[i];
        if (l >= rq || r <= lq) return INF;
        int m = (r+l)/2;
        return min(get(i*2+1, l, m, lq, rq), get(i*2+2, m, r, lq, rq));
    }
};

void solve(int n, int x, vector<int>&a) {
    vector<priority_queue<int> >mm(n);
    priority_queue<int> quee;
    for (int i = 0; i < n; i++) {
        mm[a[i]].push(-i);
    }
    mm[a[0]].pop();
    vector<int>mi(n, INF);
    for (int i = 0; i < n; i++) {
        if (mm[i].empty()) continue;
        mi[i] = -mm[i].top();
    }
    D_O tree(mi);
    vector<int>que(n, 0); int last = a[0]; 
    for (int i = 1; i < n; i++) {
        int m = min(tree.get(0, 0, n, 0, last), tree.get(0, 0, n, last+1, n));
        if (m == INF) m = -mm[last].top();
        que[i] = m;
        mm[a[m]].pop();
        if (mm[a[m]].empty()) mi[a[m]] = INF;
        else mi[a[m]] = -mm[a[m]].top();
        tree.update(0, 0, n, a[m], mi[a[m]]);
        last = a[m];
    }
    vector<int>when(n);
    for (int i = 0; i < n; i++) {
        when[que[i]] = i;
    }
    cout << when[x]+1 << '\n';
}

int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<int>a(n);
    for (int i = 0; i < n; i++) {cin >> a[i]; a[i]--;}
    for (int i = 0; i < q; i++) {
        int t, x; cin >> t >> x;
        if (t == 1) {
            swap(a[x-1], a[x]);
        } else {
            solve(n, x-1, a);
        }
    }
    return 0;
}