#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
using ll = long long;
using ld = long double;
using vl = __int128_t;
using ull = unsigned long long;
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
constexpr int mod = 998244353;
const int INF = 1e9;
struct segtree {
    vector<int>tree;
    segtree(int n) {
        tree.resize(n * 4, INF);
    }
    void reinit(int n) {
        tree.assign(n * 4, INF);
    }
    void update(int v, int l, int r, int i, int x) {
        if (l == r - 1) {
            tree[v] = x;
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            update(2 * v + 1, l, m, i, x);
        } else {
            update(2 * v + 2, m, r, i, x);
        }
        tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
    }
    int get(int v, int l, int r, int ql, int qr) {
        if (l >= qr || ql >= r) {
            return INF;
        } else if (ql <= l && r <= qr) {
            return tree[v];
        }
        int m = (l + r) / 2;
        return min(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
    }
};
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    vector<pair<int,int>> queries(q);
    int t1 = 0, t2 = 0;
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].first >> queries[i].second;
        t1 += (queries[i].first == 1);
        t2 += (queries[i].first == 2);
    }
    t2 = -1;
    vector<int> ord;
    vector<vector<int>>inds(n + 1);
    for (int i = 0; i < n; ++i) {
        inds[a[i]].pb(i);
    }
    segtree st(n + 1);
    vector<int>cur(n + 1);
    for (int i = 1; i <= n; ++i) {
        inds[i].pb(INF);
        st.update(0, 0, n + 1, i, inds[i][0]);
    }
    int tek = 0;
    for (int it = 0; it < n; ++it) {
        int nxt = min(st.get(0, 0, n + 1, 1, tek), st.get(0, 0, n + 1, tek + 1, n + 1));
        if (nxt==INF) {
            ord.pb(inds[tek][cur[tek]++]);
        } else {
            int val = a[nxt];
            ord.pb(nxt);
            cur[val]++;
            if (cur[val] == inds[val].size()) {
                st.update(0, 0, n + 1, val, INF);
            } else {
                st.update(0, 0, n + 1, val, inds[val][cur[val]]);
            }
            tek = a[nxt];
        }
    }
    for (auto[t,x] : queries) {
        if (t == 1) {
            swap(a[x - 1], a[x]);
            if (t2 >= t1) {
                ord.clear();
                inds.clear();
                inds.resize(n + 1);
                for (int i = 0; i < n; ++i) {
                    inds[a[i]].pb(i);
                }
                st.reinit(n + 1);
                cur.assign(n + 1, 0);
                for (int i = 1; i <= n; ++i) {
                    inds[i].pb(INF);
                    st.update(0, 0, n + 1, i, inds[i][0]);
                }
                tek = 0;
                for (int it = 0; it < n; ++it) {
                    int nxt = min(st.get(0, 0, n + 1, 1, tek), st.get(0, 0, n + 1, tek + 1, n + 1));
                    if (nxt==INF) {
                        ord.pb(inds[tek][cur[tek]++]);
                    } else {
                        int val = a[nxt];
                        ord.pb(nxt);
                        cur[val]++;
                        if (cur[val] == inds[val].size()) {
                            st.update(0, 0, n + 1, val, INF);
                        } else {
                            st.update(0, 0, n + 1, val, inds[val][cur[val]]);
                        }
                        tek = val;
                    }
                }
            }
        } else {
            if (t1 > t2) {
                ord.clear();
                inds.clear();
                inds.resize(n + 1);
                for (int i = 0; i < n; ++i) {
                    inds[a[i]].pb(i);
                }
                st.reinit(n + 1);
                cur.assign(n + 1, 0);
                for (int i = 1; i <= n; ++i) {
                    inds[i].pb(INF);
                    st.update(0, 0, n + 1, i, inds[i][0]);
                }
                tek = 0;
                for (int it = 0; it < n; ++it) {
                    int nxt = min(st.get(0, 0, n + 1, 1, tek), st.get(0, 0, n + 1, tek + 1, n + 1));
                    if (nxt==INF) {
                        ord.pb(inds[tek][cur[tek]++]);
                    } else {
                        int val = a[nxt];
                        ord.pb(nxt);
                        cur[val]++;
                        if (cur[val] == inds[val].size()) {
                            st.update(0, 0, n + 1, val, INF);
                        } else {
                            st.update(0, 0, n + 1, val, inds[val][cur[val]]);
                        }
                        tek = val;
                    }
                }
            }
            int id = -1;
            for (int i = 0; i < n; ++i) {
                if (ord[i] + 1 == x) {
                    id = i + 1;
                }
            }
            cout << id << '\n';
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
