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

#ifndef DEBUG
// #pragma GCC optimize("avx2")
// #pragma GCC optimize("O3")
#endif

using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
template<typename T>
using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pll = std::pair<ll, ll>;

const ll MOD = 998244353;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

std::vector<ll> num, a;

void upd() {
    ll l = 0, l1 = 0;
    num[0] = 0;
    std::vector<ll> used(a.size());
    used[0] = 1;
    int i = 1;
    ll n = a.size();
    for (; l < a.size() && l1 < a.size() && i < a.size(); ++i) {
        if (i % 2) {
            while (l1 < n && (used[l1] || a[l1] == a[l])) {
                ++l1;
            }
            if (l1 == n) break;
            used[l1] = 1;
            num[l1] = i;
        }
        else {
            while (l < n && (used[l] || a[l] == a[l1])) {
                ++l;
            }
            if (l == n) break;
            used[l] = 1;
            num[l] = i;
        }
    }
    while (l1 < n - 1) {
        if (!used[++l1]) {
            num[l1] = i++;
        }
    }
    while (l < n - 1) {
        if (!used[++l]) {
            num[l] = i++;
        }
    }
}

void solve() {
    ll n, q;
    std::cin >> n >> q;
    num.resize(n);
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    upd();
    while (q--) {
        ll t;
        std::cin >> t;
        if (t == 1) {
            ll x;
            std::cin >> x;
            --x;
            std::swap(a[x], a[x + 1]);
            upd();
        }
        else {
            ll y;
            std::cin >> y;
            --y;
            std::cout << num[y] + 1 << '\n';
        }
    }
}

int main() {
#ifdef DEBUG
    std::freopen("input.txt", "r", stdin);
#endif
    std::cin.tie(0)->std::ios::sync_with_stdio(0);
    int tt = 1;
    // std::cin >> tt;
    while (tt--) {
        solve();
    }
}
