#include "bits/extc++.h"

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<long long, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

random_device rd;
mt19937 rnd(rd());

// #pragma GCC optimize("O3", "unorll-loops")
// #pragma GCC target("avx2", "bmi", "bmi2", "popcnt", "lzcnt")

int rand(int l, int r) {
    if (r < l) assert(false);
    return uniform_int_distribution<int>(l, r)(rnd);
}

struct Segtree {
    vector<pair<int, int>> tree;
    int n;

    explicit Segtree(int n) {
        this->n = n;
        tree.resize(n * 4 + 1);
    }

    void update(int x, int l, int r, int lx, int rx, pair<int, int> val) {
        if (lx >= r || rx <= l) return;
        if (l <= lx && rx <= r) {
            tree[x] = val;
            return;
        }

        int mx = (lx + rx) / 2;

        update(x * 2 + 1, l, r, lx, mx, val);
        update(x * 2 + 2, l, r, mx, rx, val);

        tree[x].first = tree[x * 2 + 1].first + tree[x * 2 + 2].first;
        tree[x].second = tree[x * 2 + 1].second + tree[x * 2 + 2].second;
    }

    void update(int l, int r, pair<int, int> val) {
        update(0, l, r, 0, n, val);
    }

    pair<int, int> get(int x, int l, int r, int lx, int rx) {
        if (lx >= r || rx <= l) return {0, 0};
        if (l <= lx && rx <= r) return tree[x];

        int mx = (lx + rx) / 2;

        pair<int, int> a = get(x * 2 + 1, l, r, lx, mx);
        pair<int, int> b = get(x * 2 + 2, l, r, mx, rx);

        return {a.first + b.first, a.second + b.second};
    }

    pair<int, int> get(int l, int r) {
        return get(0, l, r, 0, n);
    }
};

struct Segtree_min {
    struct node {
        int val = 1e9, push = 1e9;
    };
    vector<node> tree;
    int n;

    explicit Segtree_min(int n) {
        this->n = n;
        tree.resize(n * 4 + 1);
    }

    void push(int x) {
        if (tree[x].push == 1e9) return;
        tree[x * 2 + 1].val = tree[x].push;
        tree[x * 2 + 2].val = tree[x].push;
        tree[x * 2 + 1].push = tree[x].push;
        tree[x * 2 + 2].push = tree[x].push;
        tree[x].push = 1e9;
    }

    void update(int x, int l, int r, int lx, int rx, int val) {
        if (lx >= r || rx <= l) return;
        if (l <= lx && rx <= r) {
            tree[x].val = val;
            tree[x].push = val;
            return;
        }

        int mx = (lx + rx) / 2;
        push(x);

        update(x * 2 + 1, l, r, lx, mx, val);
        update(x * 2 + 2, l, r, mx, rx, val);

        tree[x].val = min(tree[x * 2 + 1].val, tree[x * 2 + 2].val);
    }

    void update(int l, int r, int val) {
        update(0, l, r, 0, n, val);
    }

    int get(int x, int l, int r, int lx, int rx) {
        if (lx >= r || rx <= l) return 1e9;
        if (l <= lx && rx <= r) return tree[x].val;

        int mx = (lx + rx) / 2;
        push(x);

        int a = get(x * 2 + 1, l, r, lx, mx);
        int b = get(x * 2 + 2, l, r, mx, rx);

        return min(a, b);
    }

    int get(int l, int r) {
        return get(0, l, r, 0, n);
    }
};


struct node {
    int cnt = 0;
    int lead = -1;
};

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> s(n), num(n);
    vector<node> par_group(n);

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    Segtree_min st_min(n);

    par_group[0].cnt = 1;
    par_group[0].lead = 0;
    st_min.update(0, 1, 0);

    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            st_min.update(i, i + 1, st_min.get(i - 1, i));
            par_group[st_min.get(i, i + 1)].cnt++;
            continue;
        }

        st_min.update(i, i + 1, i);
        par_group[i].lead = i;
        par_group[i].cnt = 1;
    }

    int now = 1;
    vector<int> used(n + 1);

    for (int i = 0; i < n; ) {
        while (used[now]) now++;
        used[now] = true;
        int ind_group = st_min.get(i, i + 1);
        int st_a = s[i];
        num[i] = now;

        int x = min(par_group[ind_group].cnt - 1,  n - par_group[ind_group].cnt - now + 1);

        while (i + 1 < n && st_a == s[i + 1]) {
            if (x) num[i + 1] = num[i] + 2, x--;
            else num[i + 1] = num[i] + 1;
            used[num[i + 1]] = true;
            i++;
        }
        i++;
    }

    vector<pair<int, int>> val(n);
    for (int i = 0; i < n; i++) {
        int ind_group = st_min.get(i, i + 1);
        int lead = par_group[ind_group].lead;

        st_min.update(i, i + 1, lead);

        if (num[i] & 1) val[lead].first++;
        else val[lead].second++;
    }

    Segtree st(n);

    for (int i = 0; i < n; i++) {
        st.update(i, i + 1, val[i]);
    }

    auto find_num = [&](int ind) {
        int lead = st_min.get(ind, ind + 1);
        pair<int, int> v = st.get(0, lead);

        int mines = min(v.first * 2 + 1, v.second * 2 + 2);
        int x = min(par_group[lead].cnt - 1,  n - par_group[lead].cnt - mines + 1);
        int jump = ind - lead;

        mines += min(jump, x) * 2;
        jump -= min(jump, x);
        mines += min(jump, par_group[lead].cnt - x - 1);

        return mines;
    };

    auto split_fir = [&](int ind) {
        int ind_group = st_min.get(ind, ind + 1);
        par_group[ind_group].cnt--;

        st_min.update(ind, ind + 1, ind);
        par_group[ind].cnt = 1;
    };

    auto join_fir = [&](int ind) {
        if (ind == 0 || s[ind] != s[ind - 1]) return;

        int ind_group = st_min.get(ind, ind + 1);
        par_group[ind_group].cnt = 0;
        st.update(ind, ind + 1, {0, 0});

        st_min.update(ind, ind + 1, st_min.get(ind - 1, ind));

        ind_group = st_min.get(ind, ind + 1);

        par_group[ind_group].cnt++;
    };

    auto split_sec = [&](int ind) {
        int ind_group = st_min.get(ind, ind + 1);
        auto par = par_group[ind_group];

        if (par.cnt == 1) return;

        par_group[ind_group].cnt--;

        int len = par_group[ind_group].cnt;
        par_group[ind_group + 1].cnt = par_group[ind_group].cnt;

        st_min.update(ind, ind + 1, ind);
        ind_group = ind;

        par_group[ind_group].cnt = 1;

        st_min.update(ind + 1, ind + len + 1, ind + 1);
    };

    auto join_sec = [&](int ind) {
        if (ind == n - 1 || s[ind] != s[ind + 1]) return;

        int ind_group = st_min.get(ind, ind + 1);
        par_group[ind_group].cnt = 0;

        st.update(ind, ind + 1, {0, 0});

        int len = par_group[ind + 1].cnt;

        st_min.update(ind, ind + len, ind);

        par_group[ind].cnt = len + 1;
    };

    auto change = [&](int ind) {
        int lead = st_min.get(ind, ind + 1);
        int start = find_num(lead);

        st.update(lead, lead + 1, {0, 0});

        int x = min(par_group[lead].cnt - 1,  n - par_group[lead].cnt - start + 1);

        int lead_vals = x + 1 + (par_group[lead].cnt - x - 1) / 2;
        int not_lead_vals = par_group[lead].cnt - lead_vals;

        if (start & 1) {
            st.update(lead, lead + 1, {lead_vals, not_lead_vals});
        } else {
            st.update(lead, lead + 1, {not_lead_vals, lead_vals});
        }
    };


    while (q--) {
        int t, ind; cin >> t >> ind;
        ind--;

        if (t == 1) {
            if (s[ind] == s[ind + 1]) continue;

            swap(s[ind], s[ind + 1]);

            split_fir(ind);
            join_fir(ind);
            change(ind);
            if (ind != 0) change(ind - 1);

            split_sec(ind + 1);
            join_sec(ind + 1);
            change(ind + 1);
            if (ind != n - 1) change(ind + 2);
            continue;
        }

        cout << find_num(ind) << '\n';
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("answer.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int akbalin = 1;
    // cin >> akbalin;

    while (akbalin--) solve();
}