#include <bits/stdc++.h>

using namespace std;

#define sll __int128_t
#define ll long long
#define ld long double
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define size(x) (int)(x).size()

const int MOD = 998244353, MAXN = 5e5 + 100, inf = 1e9;

int add(int a, int b) {
    if (a + b >= MOD) {
        return a + b - MOD;
    }
    return a + b;
}

int sub(int a, int b) {
    if (a - b < 0) {
        return a - b + MOD;
    }
    return a - b;
}

int mult(int a, int b) {
    return ((ll)a * b) % MOD;
}

int kv(int a) {
    return ((ll)a * a) % MOD;
}

int fast_pow(int x, int a) {
    if (a == 0) return 1;
    if (a == 1) return x;
    if (a & 1) return fast_pow(x, fast_pow(x, a - 1));
    return kv(fast_pow(x, a / 2));
}

pair<int, int> d[4 * MAXN];
int a[MAXN];

void build(int v, int l, int r) {
    if (l + 1 == r) {
        d[v].first = d[v].second = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * v + 1, l, m);
    build(2 * v + 2, m, r);
    d[v].first = min(d[2 * v + 1].first, d[2 * v + 2].first);
    d[v].second = max(d[2 * v + 1].second, d[2 * v + 2].second);
}

void update(int v, int l, int r, int i) {
    if (l + 1 == r) {
        d[v].first = inf;
        d[v].second = -inf;
        return;
    }
    int m = (l + r) / 2;
    if (i < m) update(2 * v + 1, l, m, i);
    else update(2 * v + 2, m, r, i);
    d[v].first = min(d[2 * v + 1].first, d[2 * v + 2].first);
    d[v].second = max(d[2 * v + 1].second, d[2 * v + 2].second);
}

int getf(int v, int l, int r, int p) {
    if (l + 1 == r) return l;
    int m = (l + r) / 2;
    // cout << 2 * v + 1 << " " << d[2 * v + 1].first << " " << d[2 * v + 1].second << " " << p << endl;
    if (d[2 * v + 1].first > d[2 * v + 1].second || d[2 * v + 1].first == d[2 * v + 1].second && d[2 * v + 1].first == p) {
        return getf(2 * v + 2, m, r, p);
    }
    return getf(2 * v + 1, l, m, p);
}

vector<int> get(int n) {
    build(0, 0, n);
    vector<int> pl(n);
    int p = -1;
    for (int i = 0; i < n; i++) {
        if (p == -1 || d[0].first == d[0].second && d[0].first == a[p]) {
            int x = getf(0, 0, n, -1);
            update(0, 0, n, x);
            pl[x] = i + 1;
            p = x;
        }
        else {
            int x = getf(0, 0, n, a[p]);
            update(0, 0, n, x);
            pl[x] = i + 1;
            p = x;
        }
    }
    return pl;
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i]; a[i]--;
    }
    vector<int> pl = get(n);
    bool f = 0;
    for (int i = 0; i < q; i++) {
        int t, x;
        cin >> t >> x;
        x--;
        if (t == 2) {
            if (f) {
                pl = get(n);
                f = 0;
            }
            cout << pl[x] << "\n";
        }
        else {
            swap(a[x], a[x + 1]);
            f = 1;
            // if (pr[x] == -1) {
            //     swap(pr[i], pr[i + 1]);
            //     swap(nxt[i], nxt[i + 1]);
            //     pr[nxt[i]] = i;
            //     pr[nxt[i + 1]] = i + 1;
            //     swap(a[i], a[i + 1]);
            // }
            // else if (a[pr[i]] == a[i + 1]) {
            //     swap(pr[i], pr[i + 1]);
            //     swap(pl[i], pl[i + 1]);
            //     swap(nxt[i], nxt[i + 1]);
            //     pr[nxt[i]] = i;
            //     pr[nxt[i + 1]] = i + 1;
            //     swap(a[i], a[i + 1]);
            // }
            // else if (a[pr[i + 1]] == a[i]) {
            //     swap(pr[i], pr[i + 1]);
            //     swap(pl[i], pl[i + 1]);
            //     swap(nxt[i], nxt[i + 1]);
            //     pr[nxt[i]] = i;
            //     pr[nxt[i + 1]] = i + 1;
            //     swap(a[i], a[i + 1]);
            // }
            // else {
            //     swap(pr[i], pr[i + 1]);
            //     swap(nxt[i], nxt[i + 1]);
            //     pr[nxt[i]] = i;
            //     pr[nxt[i + 1]] = i + 1;
            //     swap(a[i], a[i + 1]);
            // }
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int ttt = 1;
    //cin >> ttt;
    while (ttt--) {
        solve();
    }
}