// # define _GLIBCXX_DEBUG
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("trapv")
#include <bits/extc++.h>

using namespace std;

template<typename T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update>;

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());


vector<pii> block;
vector<int> a;

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#elif DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);

    int n, q;
    cin >> n >> q;
    a.resize(n);
    vector<set<int> > ind(n + 1);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ind[x].insert(i);
        a[i] = x;
    }
    set<pii> near; // ind, color
    for (int i = 1; i <= n; ++i) {
        if (!ind[i].empty()) {
            near.emplace( *ind[i].begin(),i);
        }
    }
    while (q--) {

        for (auto &elem: ind)
            elem.clear();
        for (int i = 0; i < n; ++i)
            ind[a[i]].insert(i);
        near.clear();
        for (int i = 1; i <= n; ++i) {
            if (!ind[i].empty()) {
                near.emplace(*ind[i].begin(),i);
            }
        }

        int t, x;
        cin >> t >> x;
        --x;
        if (t == 1) {

            int c1 = a[x];
            int c2 = a[x + 1];
            if (c1 == c2) {
                continue;
            }
            swap(a[x], a[x + 1]);
            ind[c1].erase(x);
            ind[c2].erase(x + 1);

            ind[c1].insert(x + 1);
            ind[c2].insert(x);

        } else {


            int last = -1;
            int ans = 0;
            while (true) {
                pii fir = *near.begin();
                ++ans;

                if (fir.second != last) {
                    if (fir.first == x)
                        break;
                    near.erase(near.begin());

                    last = fir.second;
                    ind[fir.second].erase(ind[fir.second].begin());

                    if (!ind[fir.second].empty()) {

                        near.emplace(*ind[fir.second].begin(), fir.second);
                    }
                } else {
                    auto now = near.begin();

                    if (near.size() != 1) {
                        ++now;
                        fir = *now;
                    }
                    if (fir.first == x)
                        break;
                    near.erase(now);

                    last = fir.second;
                    ind[fir.second].erase(ind[fir.second].begin());

                    if (!ind[fir.second].empty()) {

                        near.emplace(*ind[fir.second].begin(), fir.second);
                    }
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}
