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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define all(a) a.begin(), a.end()

const int mod = 998244353;
const int inf = 1e18;

int fpm(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2 == 1) {
        return (fpm(a, b-1) * a)%mod;
    }
    int x = fpm(a, b/2);
    return (x*x)%mod;
}

struct node {
    int v;
    node(int _v = 0) {
        v = _v;
    }
};

node f(node &a, node &b) {
    return {a.v + b.v};
}

struct sgt {
    int n;
    vector<node> t;
    vector<int> p;

    void build(int v, int l, int r, vector<int> &a) {
        if (r-l == 1) {
            if (l < a.size()) {
                t[v].v = a[l];
            }
            return;
        }
        int m = (l+r)/2;
        build(2*v+1, l, m, a);
        build(2*v+2, m, r, a);
        t[v] = f(t[2*v+1], t[2*v+2]);
    }

    sgt(vector<int> &a) {
        n = 1;
        while (n < a.size()) {
            n *= 2;
        }
        t.assign(2*n-1, node());
        p.assign(2*n-1, 0);
        build(0, 0, n, a);
    }

    void apply(int v, int x) {
        t[v].v += x;
        p[v] += x;
    }

    void push(int v, int l, int r) {
        if (r-l == 1 || p[v] == 0) {
            return;
        }
        apply(2*v+1, p[v]);
        apply(2*v+2, p[v]);
        p[v] = 0;
    }

    node get(int v, int l, int r, int lq, int rq) {
        if (l >= lq && r <= rq) {
            return t[v];
        }
        if (r <= lq || rq <= l) {
            return node();
        }
        push(v, l, r);
        int m = (l+r)/2;
        node a = get(2*v+1, l, m, lq, rq);
        node b = get(2*v+2, m, r, lq, rq);
        return f(a, b);
    }

    node get(int l, int r) {
        r++;
        return get(0, 0, n, l, r);
    }

    void upd(int v, int l, int r, int lq, int rq, int x) {
        if (l >= lq && r <= rq) {
            apply(v, x);
            return;
        }
        if (r <= lq || rq <= l) {
            return;
        }
        push(v, l, r);
        int m = (l+r)/2;
        upd(2*v+1, l, m, lq, rq, x);
        upd(2*v+2, m, r, lq, rq, x);
        t[v] = f(t[2*v+1], t[2*v+2]);
    }

    void upd(int l, int r, int x) {
        r++;
        upd(0, 0, n, l, r, x);
    }
};

mt19937 rd;
uniform_int_distribution<> d(1, 3);
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> b(n);
    b[0] = 0;
    vector<int> used(n);
    used[0] = 1;
    int c = 0;
    vector<int> pred(n);
    vector<int> ord(n);
    ord[0] = 0;
    for (int i = 1; i < n; ++i) {
        int k = -1;
        for (int j = 0; j < n; ++j) {
            if (!used[j]) {
                if (a[j] != c) {
                    k = j;
                    break;
                }
            }
        }
        if (k == -1) {
            for (int j = 0; j < n; ++j) {
                if (!used[j]) {
                    k = j;
                    break;
                }
            }
        }
        used[k] = 1;
        b[k] = i;
        c = a[k];
        pred[k] = c;
        ord[i] = k;
    }
    // for (int i = 0; i < n; ++i) {
    //     cout << b[i] << " ";
    // }
    // cout << '\n';
    while (q--) {
        int t;
        cin >> t;
        int x;
        cin >> x;
        x--;
        if (t == 1) {
            if (a[x] != a[x+1]) {
                if (b[x] < b[x+1]) {
                    int c = pred[x];
                    if (b[x+1] != c) {
                        int r = b[x+1] + 1;
                        int o = 0;
                        while (r < n-1 && a[ord[r]] == a[x]) {
                            int f = ord[r];
                            int s = ord[r+1];
                            swap(b[f], b[s]);
                            swap(ord[r], ord[r+1]);
                            r += 2;
                        }
                        if (r == b[x+1] + 1) {
                            if (r < n-1 && a[ord[r+1]] == a[x+1]) {
                                int uwu = ord[r+1];
                                while (r < n-1 && a[ord[r+1]] == a[uwu]) {
                                    int f = ord[r];
                                    int s = ord[r+1];
                                    swap(b[f], b[s]);
                                    swap(ord[r], ord[r+1]);
                                    r += 2;
                                }
                            }
                        }
                    }else {
                        swap(b[x],  b[x+1]);
                        swap(ord[b[x]], ord[b[x+1]]);
                    }
                }
                else {
                    swap(b[x], b[x+1]);
                    swap(ord[b[x]], ord[b[x+1]]);
                }
            }
            swap(a[x], a[x+1]);
            // for (int i = 0; i < n; ++i) {
            //     cout << b[i] << " ";
            // }
            // cout << '\n';
        }else {
            cout << b[x]+1 << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << '\n';
    }
}