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

#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long

using pii = pair <int, int>;
const int inf = 1e12;

vector <int> a;

using oset = tree <int, null_type, less <>, rb_tree_tag, tree_order_statistics_node_update>;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q; cin >> n >> q;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <oset> match(3);
    for (int i = 0; i < n; ++i) match[a[i]].insert(i);
    while (q--) {
        int type, i; cin >> type >> i;
        i--;
        if (type == 1) {
            if (a[i] != a[i + 1]) {
                match[a[i]].erase(i);
                match[a[i]].insert(i + 1);
                match[a[i + 1]].erase(i + 1);
                match[a[i + 1]].insert(i);
            }
        } else {
            int pref = min((int)match[1].size(), (int)match[2].size());
            int id = match[a[i]].order_of_key(i + 1);
            if (id > pref) {
                cout << pref + id << '\n';
            } else {
                cout << 2 * (id - 1) + (a[id] != a[0]) << '\n';
            }

        }
    }

}