#ifdef LOCAL
#define GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

constexpr ll mod = 1e9 + 7;

mt19937_64 rnd(28);

ll randint(ll l, ll r) {
    return l + rnd() % (r - l + 1);
}

ll add(ll a, ll b) {
    if (a + b >= mod) {
        return a + b - mod;
    }
    return a + b;
}

ll sub(ll a, ll b) {
    if (a - b < 0) {
        return a - b + mod;
    }
    return a - b;
}

ll mult(ll a, ll b) {
    return __int128(a) * b % mod;
}

ll binp(ll a, ll x) {
    ll ans = 1;
    while (x > 0) {
        if (x & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        x /= 2;
    }
    return ans;
}

ll divd(ll a, ll b) {
    return mult(a, binp(b, mod - 2));
}

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ll f = 1;
    for (int i = 0; i < n; ++i) {
        if (a[i] != a[0]) {
            f = 0;
        }
    }
    if (f) {
        while (q--) {
            ll ti, x;
            cin >> ti >> x;
            if (ti == 2) {
                cout << x << '\n';
            }
        }
        return;
    }
    vector<ll> id(n + 1), ans(n);
    vector<vector<ll>> lst(n + 1);
    while (q--) {
        ll ti, x;
        cin >> ti >> x;
        x--;
        if (ti == 1) {
            swap(a[x], a[x + 1]);
        } else {
            for (int i = 1; i <= n; ++i) {
                id[i] = 0;
                lst[i].clear();
            }
            for (int i = 0; i < n; ++i) {
                ans[i] = 0;
                lst[a[i]].emplace_back(i);
            }
            set<pair<ll, ll>> s;
            for (int i = 1; i <= n; ++i) {
                if (!lst[i].empty()) {
                    s.insert({lst[i].front(), i});
                }
            }
            ll cur = 1, last = -1;
            while (s.size() >= 2) {
                auto it = s.begin();
                if (s.begin()->second == last) {
                    it++;
                }
                auto [nm, c] = *it;
                ans[nm] = cur++;
                id[c]++;
                s.erase(it);
                last = a[nm];
                if (id[c] != lst[c].size()) {
                    s.insert({lst[c][id[c]], c});
                }
            }
            for (int i = 0; i < n; ++i) {
                if (ans[i] == 0) {
                    ans[i] = cur++;
                }
            }
            cout << ans[x] << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << endl;
    }
}