#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <random>
#include <chrono>
#include <deque>
#pragma GCC optimize("unroll-loops", "Ofast")
#pragma GCC target("avx2");
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()

void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		v[i]--;
	}

	vector<pair<int, int>> cur;
	vector<int> pos;

	auto f = [&]() {
		cur = {};
		pos.assign(n, 0);
		vector<deque<int>> wh(n);
		for (int i = 0; i < n; i++) {
			wh[v[i]].push_back(i);
		}
		set<pair<int, int>> st;
		for (int i = 0; i < n; i++) {
			if (wh[i].size())st.insert({ wh[i][0], i });
		}
		int prev = -1;
		while (st.size()) {
			if (st.size() == 1) {
				prev = -1;
			}
			auto [i, col] = *st.begin();
			st.erase(st.begin());

			if (prev != col) {
				pos[i] = cur.size();
				cur.push_back({ col ,i });
				wh[col].pop_front();
				if (wh[col].size()) {
					st.insert({ wh[col][0], col });
				}
				prev = col;
				continue;
			}
			int a = i, b = col;

			i = st.begin()->first, col = st.begin()->second;
			st.erase(st.begin());

			pos[i] = cur.size();
			cur.push_back({ col ,i });
			wh[col].pop_front();
			if (wh[col].size()) {
				st.insert({ wh[col][0], col });
			}
			prev = col;

			st.insert({ a, b });
		}
		};
	f();


	for (int rep = 0; rep < q; rep++) {
		int t;
		cin >> t;
		if (t == 1) {
			int I;
			cin >> I;
			I--;
			if (v[I] == v[I + 1])continue;
			swap(v[I], v[I + 1]);
			int i = min(pos[I + 1], pos[I]), j = max(pos[I], pos[I + 1]);
			if (i && cur[i - 1].first == cur[j].first) {
				swap(pos[I], pos[I + 1]);
				swap(cur[i].second, cur[j].second);
				continue;
			}
			int k = cur[i].first, z = cur[i + 1].first;
			swap(cur[i].first, cur[i + 1].first);
			i += 2;
			for (; i + 1 < cur.size(); i += 2) {
				if (cur[i].first == cur[i - 1].first || cur[i + 1].first != cur[i - 1].first && cur[i + 1].second < cur[i].second) {
					swap(pos[cur[i].second], pos[cur[i + 1].second]);
					swap(cur[i], cur[i + 1]);
				}
			}
			vector<pair<int,int>> tp;
			while (cur.size() && (tp.size() == 0 || cur.back().first == tp.back().first)) {
				tp.push_back(cur.back());
				cur.pop_back();
			}
			sort(all(tp));
			for (auto x : tp) {
				pos[x.second] = cur.size();
				cur.push_back(x);
			}
		}
		else {
			int i;
			cin >> i;
			i--;
			cout << pos[i] + 1 << "\n";
		}
	}

}

signed main() {
	srand(time(0));
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
}
