#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>

using namespace std;
using ll = long long;

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

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

const ll MOD = 998'244'353;

map<ll, set<ll>> colors;
vector<ll> gen(ll n, vector<ll>& a) {
	vector<ll> ans(n);
	ans[0] = 1;
	ll color = a[0];
	set<pair<ll, ll>> vals;
	for (auto& i : colors) {
		vals.insert({ *i.second.begin(), i.first });
	}
	vals.erase(vals.begin());
	if (colors[a[0]].size() > 1) {
		vals.insert({ *colors[a[0]].upper_bound(0), color });
	}
	ll cnt = 2;
	while (!vals.empty()) {
		pair<ll, ll> y = *vals.begin();
		if (y.second != color || vals.size() == 1) {
			vals.erase(vals.begin());
			ans[y.first] = cnt++;
			auto res = colors[y.second].upper_bound(y.first);
			if (res != colors[y.second].end()) {
				vals.insert({ *res, y.second });
			}
			color = y.second;
		}
		else {
			y = *(++vals.begin());
			vals.erase(++vals.begin());
			ans[y.first] = cnt++;
			auto res = colors[y.second].upper_bound(y.first);
			if (res != colors[y.second].end()) {
				vals.insert({ *res, y.second });
			}
			color = y.second;
		}
	}
	return ans;
}

void solve() {
	ll n, q; cin >> n >> q;
	vector<ll> a(n); cin >> a;
	for (ll i = 0; i < n; i++) {
		colors[a[i]].insert(i);
	}
	vector<ll> ans;
	ll change = 1;
	while (q--) {
		ll t, x; cin >> t >> x;
		if (t == 1) {
			x--;
			colors[a[x]].erase(x);
			colors[a[x + 1]].erase(x + 1);

			colors[a[x]].insert(x + 1);
			colors[a[x + 1]].insert(x);
			swap(a[x], a[x + 1]);
			change = 1;
		}
		else {
			if (change) ans = gen(n, a);
			change = 0;
			cout << ans[x - 1] << '\n';
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

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