#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//#define int long long

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
//#define endl "\n"

template<class T>
istream& operator >> (istream& in, pair<T, T>& a) {
    in >> a.first >> a.second;
    return in;
}
template<class T>
istream& operator >> (istream& in, vector<T>& a) {
    for (T& x : a){
        in >> x;
    }
    return in;
}
template<class T>
ostream& operator << (ostream& out, pair<T, T> a) {
    out << a.first << " " << a.second << " ";
    return out;
}
template<class T>
ostream& operator << (ostream& out, vector<T> a) {
    for (auto& x : a) {
        out << x << " ";
    }
    return out;
}
#define debug(x) cout << (#x) << ": " << (x) << endl

void calc(int n, vi& a, vi& ord) {
    vector<vi> ind(n);
    set<int> st;
    for (int i = 0; i < n; i++) {
        ind[a[i]].push_back(i);
        if (ind[a[i]].size() == 1) {
            st.insert(i);
        }
    }
    for (int x = 0; x < n; x++) {
        reverse(all(ind[x]));
    }
    int last = -1;
    int cnt = 0;
    while (st.size() > 1) {
        // cout << endl;
        // debug(cnt);
        int i = *st.begin();
        int x = a[i];
        if (x == last) {
            auto it = st.begin();
            it++;
            i = *it;
            x = a[i];
            st.erase(it);
        }
        else {
            st.erase(st.begin());
        }

        ind[x].pop_back();
        if (!ind[x].empty()) {
            st.insert(ind[x].back());
        }

        ord[i] = cnt + 1;
        cnt++;
        last = x;
    }

    int i = *st.begin();
    int x = a[i];
    while (!ind[x].empty()) {
        ord[ind[x].back()] = cnt + 1;
        cnt++;
        ind[x].pop_back();
    }
}

vi brute(int n, int q, vi a, vector<pi>& qq) {
    vi ord(n);
    calc(n, a, ord);
    int last_t = -1;
    vi ans;
    for (auto [t, i] : qq) {
        // cout << t << " " << i << endl;
        // debug(ord);
        if (t == 1) {
            swap(a[i - 1], a[i]);
        }
        else {
            if (last_t == 1) {
                calc(n, a, ord);
            }
            ans.push_back(ord[i - 1]);
        }
        last_t = t;
    }
    return ans;
}

void solve() {
    int n, q; cin >> n >> q;
    vi a(n); cin >> a;
    for (auto& x : a) x--;
    vector<pi> qq(q);
    cin >> qq;

    if (true) {
        cout << brute(n, q, a, qq) << endl;
        return;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
