#include<iostream>
#include<set>
#include<vector>
#pragma GCC optimize("Ofast")
using namespace std;

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

const ll infl = (ll)4e18 + 100;
const ll infi = (ll)1e9 + 100;
const ll maxn = (ll)1e6 + 10;
const ll mod = (ll)1e9 + 7;

inline void solve() {
	ll n, q; cin >> n >> q;
	vector<ll> a(n + 1);
	vector<set<ll>> ps(n + 1);
	/*cout << "ps:\n";
	for (ll i = 1; i <= n; ++i) {
		cout << i << ": ";
		for (auto& el : ps[a[i]])
			cout << el << " ";
		cout << '\n';
	}
	cout << "--------------\n";*/
	for (ll i = 1; i <= n; ++i) {
		cin >> a[i]; // cout << a[i] << "<<<<<<<<<<\n";
		ps[a[i]].insert(i);

		/*cout << "ps:\n";
		for (ll i = 1; i <= n; ++i) {
			cout << i << ": ";
			for (auto& el : ps[a[i]])
				cout << el << " ";
			cout << '\n';
		}
		cout << "--------------\n";*/
	}

	while (q--) {
		ll tp; cin >> tp;
		if (tp == 1) {
			ll x; cin >> x;

			if (a[x] != a[x + 1]) {
				ps[a[x]].erase(x); ps[a[x + 1]].erase(x + 1);
				swap(a[x], a[x + 1]);
				ps[a[x]].insert(x); ps[a[x + 1]].insert(x + 1);
			}
		}
		else {
			ll y; cin >> y;

			set<pair<set<ll>, ll>> st;
			ps[a[0]].erase(0);
			for (ll i = 1; i < n; ++i)
				if (!ps[i].empty())
					st.insert({ ps[i], i });
			ps[a[0]].insert(0);

			ll ind = 1, col = a[0];
			while (true) {
				auto it = st.begin();
				while (it != st.end() && (*it).second == col)
					++it;

				if (it == st.end())
					it = st.begin();

				auto p = *it;
				auto nw = p.first;
				auto c = p.second;

				st.erase(it);

				if (*nw.begin() == y) {
					cout << ind << '\n';
					break;
				}

				nw.erase(nw.begin());
				if (!nw.empty())
					st.insert({ nw, c });
				++ind; col = c;
			}
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll t_ = 1; // cin >> t_;
	while (t_--) {
		solve();
		cout << '\n';
	}

	return 0;
}