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

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define Vector2 pair <int, int>
#define print(a) for (const auto& x : a) cout << x << ' ';

vector <int> arr, col;
int n, q;

vector <int> solve1() {
	unordered_map<int, vector<int>> mpc;
	for (int i = 0; i < n; ++i) {
		mpc[col[arr[i]]].push_back(i);
	}
	unordered_map<int, int> ptr;
	set<Vector2> st;

	for (const auto& x : mpc) {
		ptr[x.F] = 0;
		st.insert({x.S[0], x.F});
	}
	vector <int> rnk(n + 1);
	int fst = arr[0], lst = col[fst], cur = 1;
	rnk[fst] = cur++;
	st.erase({mpc[lst][0], lst});
	ptr[lst] = 1;
	if (ptr[lst] < sz(mpc[lst])) {
		st.insert({mpc[lst][ptr[lst]], lst});
	}
	while (cur <= n) {
		if (st.empty()) {
			break;
		}
		auto it = st.begin();
		if (it->S == lst) {
			auto it2 = next(it);
			if (it2 == st.end()) {
				int c = lst;
				st.erase(it);
				while (ptr[c] < sz(mpc[c])) {
					int pos = mpc[c][ptr[c]++];
					rnk[arr[pos]] = cur++;
				}
				break;
			}
			it = it2;
		}
		int c = it->S;
		int pos = it->F;
		st.erase(it);
		rnk[arr[pos]] = cur++;
		lst = c;
		ptr[c]++;
		if (ptr[c] < sz(mpc[c])) {
			st.insert({mpc[c][ptr[c]], c});
		}
	}
	return rnk;
}

vector <int> solve2() {
	array<vector <int>,6> pbc;
	for (int i = 0; i < n; ++i) {
		pbc[col[arr[i]]].push_back(i);
	}
	array<int, 6> ptr;
	vector <int> rnk(n + 1);
	int fst = arr[0], lst = col[fst], cur = 1;
	rnk[fst] = cur++;
	ptr[lst] = 1;
	while (cur <= n) {
		int bcl = -1, bps = LLONG_MAX;
		for (int c = 1; c <= 5; ++c) {
			if (c == lst) {
				continue;
			}
			if (ptr[c] < sz(pbc[c])) {
				int pos = pbc[c][ptr[c]];
				if (pos < bps) {
					bps = pos;
					bcl = c;
				}
			}
		}
		if (bcl == -1) {
			while (ptr[lst] < sz(pbc[lst])) {
				int pos = pbc[lst][ptr[lst]++];
				rnk[arr[pos]] = cur++;
			}
		}
		int pos = pbc[bcl][ptr[bcl]++];
		rnk[arr[pos]] = cur++;
		lst = bcl;
	}
	return rnk;
}

void solve()
{
	cin >> n >> q;
	arr.resize(n);
	col.resize(n);
	bool flag = true;
	for (auto& x : col) {
		cin >> x;
		if (x < 1 || x > 5) {
			flag = false;
		}
	}
	for (int i = 0; i < n; ++i) {
		arr[i] = i;
	}
	bool c = (n > 10000 && flag);
	vector <int> cc;
	bool flag2 = true;
	while (q--) {
		int t, i;
		cin >> t >> i;
		--i;
		if (t == 1) {
			swap(arr[i], arr[i + 1]);
			flag2 = true;
		} else {
			if (c) {
				if (flag2) {
					cc = solve2();
					flag2 = false;
				}
				cout << cc[arr[i]] << '\n';
			} else {
				vector <int> ans = solve1();
				cout << ans[arr[i]] << '\n';
			}
		}
	}
}

signed main()
{
	cin.tie(nullptr)->ios_base::sync_with_stdio(false);
	solve();
	return 0;
}