#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>>pos(n);
    vector<pair<int, int>>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = pos[a[i].first - 1].size();
        pos[a[i].first - 1].push_back(i);
    }
    int t, x;
    for (int i = 0; i < q; i++) {
        cin >> t >> x;
        x--;
        if (t == 1) {
            if (a[x].first == a[x + 1].first) {
                continue;
            }
            swap(a[x], a[x + 1]);
            pos[a[x].first - 1][a[x].second] = x;
            pos[a[x + 1].first - 1][a[x + 1].second] = x + 1;
        }
        else {
            int ans = a[x].second + 1;
            int cntels;
            if (a[x].first == a[0].first) {
                cntels = ans - 1;
            } else {
                cntels = ans;
            }
            cntels = min(cntels, (int) pos[1 - x].size());
            cout << ans + cntels << endl;
        }
    }
}

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