// dimaloh

#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;
using ll = long long;
using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;

#define len(v) (int)v.size()
#define all(v) v.begin(), v.end()

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

const ll INF = 1e18;
const int inf = 1e9, mod = 1e9 + 7, sz = 5e5 + 10, logn = 20;
const ld pi = acosl(-1), eps = 1e-8;

mt19937 rnd(87438);

pii cnt[sz];

vector<vector<int>>pos;

int check(vector<int>&v, int x) {
    int n = len(v);
    int l = 0, r = n;
    int ind = -1;
    if (v[x] == 0) {
        ind = lower_bound(all(pos[0]), x) - pos[0].begin();
    } else {
        ind = lower_bound(all(pos[1]), x) - pos[1].begin();
    }
    while (r - l > 1) {
        int m = (l + r) / 2;
        int p1 = m / 2;
        int p2 = m / 2;
        if (m % 2) {
            if (v[0] == 0) {
                p1++;
            } else {
                p2++;
            }
        }

        if (p1 > len(pos[0])) {
            p2 += len(pos[0]) - p1;
            p1 = len(pos[0]);
        }
        if (p2 > len(pos[1])) {
            p1 += len(pos[1]) - p2;
            p2 = len(pos[1]);
        }

        if (v[x] == 0) {
            if (p1 > ind) {
                r = m;
            } else {
                l = m;
            }
        } else {
            if (p2 > ind) {
                r = m;
            } else {
                l = m;
            }
        }
    }
    return r;
}


void solve() {
    int n, q;
    cin >> n >> q;
    pos.assign(n, vector<int>());
    vector<int>v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        v[i]--;
        pos[v[i]].push_back(i);
    }
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x; cin >> x;
            if (v[x] == v[x - 1]) continue;

            int ind = lower_bound(all(pos[v[x - 1]]), x - 1) - pos[v[x - 1]].begin();
            pos[v[x - 1]][ind] = x;

            ind = lower_bound(all(pos[v[x]]), x) - pos[v[x]].begin();
            pos[v[x]][ind] = x - 1;

            swap(v[x], v[x - 1]);
            
        } else {
            int x; cin >> x;
            cout << check(v, x - 1) << '\n';
        }
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20);

    int t = 1;

#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    cin >> t;
#endif


    while (t--) {
        solve();
        cout << '\n';
    }
}
