#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;

struct segtree {
    ll n = 1;
    vector<map<ll, ll>> st;

    segtree(vector<ll> a) {
        while (n < a.size())
            n <<= 1;
        st.resize(n << 1);
        for (ll i = 0; i < a.size(); i++) {
            st[i + n][a[i]]++;
            ll p = i + n;
            while (p >>= 1)
                st[p][a[i]]++;
        }
    }

    void upd(ll i, ll x, ll d) {
        st[i += n][x] += d;
        while (i >>= 1)
            st[i][x] = st[i << 1][x] + st[i << 1 | 1][x];
    }

    ll get(ll l, ll r, ll x) {
        l += n, r += n;
        ll res = 0;
        while (l < r) {
            if (l & 1)
                res += st[l++][x];
            if (r & 1)
                res += st[--r][x];
            l >>= 1, r >>= 1;
        }
        return res;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, q;
    cin >> n >> q;

    vector<ll> a(n);
    for (ll &i: a)
        cin >> i;
    a.push_back(0);

    segtree st(a);
    while (q--) {
        ll i, j;
        cin >> i >> j;
        j--;

        if (i == 1) {
            st.upd(j, a[j], -1);
            st.upd(j, a[j + 1], 1);
            
            st.upd(j + 1, a[j + 1], -1);
            st.upd(j + 1, a[j], 1);
            continue;
        }
        
        if (i == 2) {
            ll k1 = st.get(0, j, 1);
            ll k2 = st.get(0, j, 2);

            if (k1 == k2) {
                cout << j + 1 << '\n';
                continue;
            }

            ll lider = (k1 > k2 ? 1 : 2);
            if (a[j] != lider) {
                cout << 2 * min(k1, k2) + 2 << '\n';
                continue;
            }

            ll cnt = max(k1, k2) - min(k1, k2);
            ll close = st.get(j + 1, n + 1, 3 - lider);

            if (close >= cnt) {
                cout << 2 * min(k1, k2) + 2 * cnt + 1 << '\n';
                continue;
            } else {
                cout << 2 * (min(k1, k2) + close) + (cnt - close) << '\n';
                continue;
            }
        }
    }


    return 0;

    while (q--) {
        ll i, j;
        cin >> i >> j;
        j--;


    }
}
