#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <vector>

// #pragma GCC optimize("O3, Ofast")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using ll = long long;

using pii = pair<int, int>;
using vi = vector<int>;
using vp = vector<pii>;
using vv = vector<vi>;

template<class T>
istream &operator>>(istream &in, vector<T> &a) {
    for (auto &i: a) {
        cin >> i;
    }
    return in;
}

template<class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
    cin >> a.first >> a.second;
    return in;
}

template<class T>
ostream &operator<<(ostream &out, vector<T> &a) {
    for (auto &i: a) {
        cout << i << ' ';
    }
    cout << '\n';
    return out;
}

void solve();

template<class T>
using oset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update>;

signed main() {
#ifdef LOCAL
    freopen(R"(C:\work\untitled\input.txt)", "r", stdin);
    freopen(R"(C:\work\untitled\output.txt)", "w", stdout);

    auto begin_ = chrono::steady_clock::now();
#else
    cin.tie(0);
    cout.tie(0);
    std::ios_base::sync_with_stdio(0);
#endif
    int t_ = 1;
    // cin >> t_;
    while (t_--) {
        solve();
    }
#ifdef LOCAL
    auto end_ = chrono::steady_clock::now();

    cout << "\n\n===========\n";
    cout << chrono::duration_cast<chrono::milliseconds>(end_ - begin_).count() << " ms";
#endif
}

//#define int ll

void solve() {
    int n, q;
    cin >> n >> q;
    vi a(n);
    cin >> a;
    vp segs;
    vi por(n);
    auto regen = [&]() {
        int mn0 = 2;
        int mn1 = 3;
        por[0] = 1;
        vi idx(3 * n, -1);
        for (int i = 1; i < n; ++i) {
            if (a[i] == a[i - 1]) {
                por[i] = por[i - 1] + 2;
                idx[por[i]] = i;
                if (por[i] % 2 == 0) {
                    mn0 = max(mn0, por[i] + 2);
                } else {
                    mn1 = max(mn1, por[i] + 2);
                }
            } else {
                if (mn0 < mn1) {
                    por[i] = mn0;
                    mn0 += 2;
                } else {
                    por[i] = mn1;
                    mn1 += 2;
                }
                idx[por[i]] = i;
            }
        }
        int p = *max_element(por.begin(), por.end());
        int id = 2 * n;
        int mx = n;
        for (int i = 2 * n; i > 0; --i) {
            if (idx[i] != -1) {
                por[idx[i]] = mx;
                mx--;
            }
        }
    };
    regen();

    for (int hi = 0; hi < q; ++hi) {
        int t, v;
        cin >> t >> v;
        v--;
        if (t == 1) {
            swap(a[v], a[v + 1]);

            regen();
        } else {
            cout << por[v] << '\n';
        }
    }
}
