#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define cin(v) for (auto& vi : v) { cin >> vi; }
#define cout(v) for (auto& vi : v) { cout << vi << ' '; } cout << '\n';
//#define int long long

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

const int INF = 1e9 + 7;
const int MOD = 998244353;
const int MOD2 = 1e9 + 737373;
const ll LINF = 1e18 + 7;
const double eps = 1e-8;
const double PI = acos(-1);

int n, m;

char used[1000073];

void model(vector <int>& vec, vector <int>& order) {
    fill(used, used + n + 1, 0);
    int l = 0, r = 0;
    int last = -1;
    int id = 0;
    while (l < n && r < n) {
        if (used[l]) {
            l++;
            continue;
        }
        if (vec[l] != last) {
            order[l] = id;
            //cout << l << ' ';
            used[l] = 1;
            id++;
            last = vec[l];
            l++;
            r = max(r, l);
        }
        else {
            while (r < l || (r < n && (vec[r] == last || used[r]))) {
                r++;
            }
            if (r < n) {
                order[r] = id;
                //cout << r << ' ';
                used[r] = 1;
                id++;
                last = vec[r];
                r++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            order[i] = id;
            //cout << i << ' ';
            id++;
        }
    }
    //cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    set <int> values;
    int differ = 0, ones = 0;
    int q;
    cin >> n >> q;
    vector <int> vec(n), pref(n + 1, 0);
    cin(vec);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + (vec[i] == 1);
        values.insert(vec[i]);
        if (vec[i] == 1) {
            ones++;
        }
    }
    differ = values.size();
    if (differ == 2 && values.contains(1) && values.contains(2)) {
        vector <int> num(n, 0);
        vector <int> ones(n + 1, 0), twos(n + 1, 0);
        for (int i = 0; i < n; i++) {
            ones[i + 1] = ones[i] + (vec[i] == 1);
            twos[i + 1] = twos[i] + (vec[i] == 2);
            if (vec[i] == 1) {
                num[i] = ones[i + 1];
            }
            else {
                num[i] = twos[i + 1];
            }
        }
        int mn = min(ones[n], twos[n]);
        while (q--) {
            int t, x;
            cin >> t >> x;
            x--;
            if (t == 1) {
                if (vec[x] == 1 && vec[x + 1] == 2) {
                    ones[x + 1]--;
                    twos[x + 1]++;
                    swap(num[x], num[x + 1]);
                }
                else if (vec[x] == 2 && vec[x + 1] == 1) {
                    ones[x + 1]++;
                    twos[x + 1]--;
                    swap(num[x], num[x + 1]);
                }
                swap(vec[x], vec[x + 1]);
            }
            else {
                int k = num[x];
                if (k <= mn) {
                    cout << k * 2 - 1 * (vec[0] == vec[x]) << '\n';
                }
                else {
                    cout << k + mn << '\n';
                }
            }
        }
    }
    else if (ones + differ - 1 == n) {
        // while (q--) {
        //     int t, x;
        //     cin >> t >> x;
        //     x--;
        //     if (t == 1) {
        //         swap(vec[x], vec[x + 1]);
        //
        //     }
        //     else {
        //         if (pref)
        //         cout <<  << '\n';
        //     }
        // }
    }
    else if (n <= 10000) {
        vector <int> order(n);
        model(vec, order);
        while (q--) {
            int t, x;
            cin >> t >> x;
            x--;
            if (t == 1) {
                swap(vec[x], vec[x + 1]);
                model(vec, order);
            }
            else {
                cout << order[x] + 1 << '\n';
            }
        }
    }
    return 0;
}