#include <bits/stdc++.h>

// #pragma GCC optimize("O3")
// // #pragma GCC optimize("Ofast")
// // #pragma GCC target("unroll_loops")

#define int long long
using ll = long long;
using ld = long double;
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>

//  using namespace __gnu_pbds;
// using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int INF = 1e18, MAXN = 1e5, mod = 998244353;

void solve();

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

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    vector<int> idx(n), last_val(n);
    int j = 0;
    int last = -1;
    deque<int> all;
    for (int i = 0; i < n; i++) {
        all.push_back(i);
        if (arr[i] != last) {
            last_val[i] = last;

            idx[i] = j;
            last = arr[i];
            j++;
            all.pop_back();
        }
        while (!all.empty() && arr[all[0]] != last) {
            last_val[all[0]] = last;

            idx[all[0]] = j;
            last = arr[all[0]];
            j++;
            all.pop_front();
        }
    }
    while (!all.empty()) {
        last_val[all[0]] = last;

        idx[all[0]] = j;
        j++;
        all.pop_front();
    }
    int cnt = 0;

    while (q--) {
        int tp, x;
        cin >> tp >> x;
        x--;
        if (tp == 1) {
            if (arr[x] == arr[x + 1]) {
                swap(arr[x], arr[x + 1]);
                continue;
            }
            if (idx[x + 1] < idx[x]) {
                swap(arr[x], arr[x + 1]);
                swap(idx[x + 1], idx[x]);
                continue;
            }
            if (last_val[x] == arr[x + 1]) {
                swap(arr[x], arr[x + 1]);
                swap(idx[x + 1], idx[x]);
                continue;
            }
            swap(arr[x], arr[x + 1]);
            cnt = 1;
            continue;
        }
        if (cnt == 1) {
            cnt = 0;
            idx.assign(n, 0);
            j = 0, last = -1;
            for (int i = 0; i < n; i++) {
                all.push_back(i);
                if (arr[i] != last) {
                    idx[i] = j;
                    last = arr[i];
                    j++;
                    all.pop_back();
                }
                while (!all.empty() && arr[all[0]] != last) {
                    idx[all[0]] = j;
                    last = arr[all[0]];
                    j++;
                    all.pop_front();
                }
            }
            while (!all.empty()) {
                idx[all[0]] = j;
                j++;
                all.pop_front();
            }
        }
        cout << idx[x] + 1 << '\n';
    }
}
