#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;

#pragma GCC optimize("O3,fast-math,unroll-loops")

int N = 5e5;
int n;

vector<int> a;

vector<vector<int>> idx;
bitset<500000> st;
vector<int> order;
vector<int> i_ord;

void build() {
	st = 0;
	for (const auto& i : idx) {
		st[i[0]] = 1;
	}

	vector<int> tmp(idx.size(), 0);

	order.clear();
	order.reserve(n);

	int cur = -1;
	for (int i = 0; i < n; i++) {
		int first = st._Find_first();

		if (a[first] == cur && st._Find_next(first) < n) {
			first = st._Find_next(first);
		}

		order.push_back(first);
		i_ord[first] = order.size();

		// cout << cur << ' ' << first << ' ' << a[first] << endl;
		cur = a[first];

		st[first] = 0;
		tmp[a[first]]++;
		if (tmp[a[first]] == idx[a[first]].size()) continue;
		st[idx[a[first]][tmp[a[first]]]] = 1;
	}
}

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

	int q;
	cin >> n >> q;
	a.resize(n);
	idx.reserve(n);

	i_ord.resize(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
		while (a[i] >= idx.size()) idx.push_back({});
		idx[a[i]].push_back(i);
	}


	build();
	// for (int i : order) {
	// 	cout << i << ' ';
	// }
	// cout << endl;
	while (q--) {
		int tp; cin >> tp;
		if (tp == 1) {
			int x; cin >> x;
			x--;

			if (a[x] == a[x + 1]) continue;

			int idx1 = lower_bound(idx[a[x]].begin(), idx[a[x]].end(), x) - idx[a[x]].begin();
			int idx2 = lower_bound(idx[a[x + 1]].begin(), idx[a[x + 1]].end(), x + 1) - idx[a[x + 1]].begin();

			// cout << endl << idx[a[x]][idx1] << ' ' << idx[a[x + 1]][idx2] << endl;
			swap(idx[a[x]][idx1], idx[a[x + 1]][idx2]);
			swap(a[x], a[x + 1]);

			build();
		} else {
			int y; cin >> y;
			y--;
			cout << i_ord[y] << ' ';
		}
	}
	return 0;
}
