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


// order_of_key
// find_by_order
using namespace __gnu_pbds;
using namespace std;
using ll = long long;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



















const ll mod = 998244353;



ll bin_pow(ll n, ll st) {
	if (st == 0) {
		return 1;
	}

	if (st % 2 == 0) {
		ll rs = bin_pow(n, st / 2);
		return (rs * rs) % mod;
	} else {
		ll rs = bin_pow(n, st / 2);
		return (((rs * rs) % mod) * n) % mod;
	}
}




vector <ll> color[500001];
ordered_set vals[500001];

ll n, q;

void build(vector <ll> &a) {
	for (ll i = 0; i <= n; i++) {
		vals[i].clear();
		color[i].clear();
	}



	for (ll i = n; i >= 2; i--) { color[a[i]].push_back(i); }
	set <pair <ll, ll>> best;
	for (ll i = 1; i <= n; i++) {
		if (!color[i].empty()) {
			best.insert({color[i][color[i].size() - 1], i});
		}
	}

	ll last_color = a[1];
	vector <ll> road = {0, 1};
	for (ll i = 2; i <= n; i++) {
		ll cur = (*best.begin()).second;
		if (cur == last_color && best.size() != 1) {
			cur = (*(++best.begin())).second;
			road.push_back(color[cur][color[cur].size() - 1]);
			best.erase(++best.begin());
			color[cur].pop_back();
			if (!color[cur].empty()) {
				best.insert({color[cur][color[cur].size() - 1], cur});
			}
			last_color = cur;
		} else {
			road.push_back(color[cur][color[cur].size() - 1]);
			best.erase(best.begin());
			color[cur].pop_back();
			if (!color[cur].empty()) {
				best.insert({color[cur][color[cur].size() - 1], cur});
			}
			last_color = cur;
		}
	}

	vector <ll> answer(n + 1);


	for (ll i = 1; i <= n; i++) {
		color[a[road[i]]].push_back(i);
		vals[a[road[i]]].insert(road[i]);
	}
}



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

	
	cin >> n >> q;

	vector <ll> a(n + 1); 

	for (ll i = 1; i <= n; i++) { cin >> a[i]; }



	// for (auto el : a) {
	// 	cout << el << ' ';
	// }
	// cout << endl;

	// cout << endl;
	// cout << road.size() << endl;

	build(a);



	while (q--) {
		ll t; cin >> t;

		if (t == 1) {
			ll x; cin >> x;

			if (x == 1) {
				swap(a[x], a[x + 1]);
				build(a);
				continue;
			}

			vals[a[x]].erase(x);
			vals[a[x + 1]].erase(x + 1);

			vals[a[x]].insert(x + 1);
			vals[a[x + 1]].insert(x);
			swap(a[x], a[x + 1]);
		} else {
			ll y; cin >> y;
			// for (auto el : color[a[y]]) {
			// 	cout << el << ' ';
			// }
			// cout << endl;

			// for (auto el : vals[a[y]]) {
			// 	cout << el << ' ';
			// }
			// cout << endl;

			cout <<  color[a[y]][vals[a[y]].order_of_key(y)] << '\n';
		}
	}
}




