#pragma GCC optimize("O3")
#include <vector>

#pragma GCC target("avx2")
#include <random>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <set>
#include <map>

using namespace std;

#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define pld pair<ld, ld>

#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>

#define vld vector<ld>
#define vvld vector<vld>
#define vvvld vector<vvld>
#define vvvvld vector<vvvld>

#define vpll vector<pll>
#define vvpll vector<vpll>
#define vvvpll vector<vvpll>
#define vvvvpll vector<vvvpll>

#define vpld vector<pld>
#define vvpld vector<vpld>
#define vvvpld vector<vvpld>
#define vvvvpld vector<vvvpld>

#define forlr(i, l, r) for(ll i = (l); i < (r); ++i)
#define forn(i, n) forlr(i, 0, n)
#define forin(x, v) for(auto& x : v)

#define all(v) v.begin(), v.end()
#define pb emplace_back

template <class T>
istream& operator>>(istream& in, vector<T>& v) {
	forin(x, v)
		in >> x;
	return in;
}

template <class T>
ostream& operator<<(ostream& out, vector<T>& v) {
	forin(x, v)
		out << x << ' ';
	return out;
}

mt19937 mt;

	struct Node {
		Node* l = 0, *r = 0;

		ll a;
		ll s = 1, p;

		Node(ll a) : a(a), p(mt()) {}
	}*root;

	ll gs(Node* t) {
		return t ? t->s : 0ll;
	}

	void upd(Node* t) {
		t->s = gs(t->l) + 1 + gs(t->r);
	}

	Node* merge(Node* l, Node* r) {
		if (!l)
			return r;
		if (!r)
			return l;

		if (l->p > r->p) {
			l->r = merge(l->r, r);
			upd(l);
			return l;
		}

		r->l = merge(l, r->l);
		upd(r);
		return r;
	}

	pair<Node*, Node*> split(Node* t, ll s) {
		if (!t)
			return { 0, 0 };
		if (gs(t->l) >= s) {
			auto [l, r] = split(t->l, s);
			t->l = r;
			upd(t);
			return { l, t };
		}

		auto [l, r] = split(t->r, s - gs(t->l) - 1);
		t->r = l;
		upd(t);
		return { t, r };
	}

vll invp(vll a) {
	ll n = a.size();
	vll ans(n);
	forn(i, n)
		ans[a[i]] = i;
	return ans;
}

vll ask(vll a) {
	ll n = a.size();
	vll ans;

	a.push_back(-1);

	//forin(x, a)
		//root = merge(root, new Node(x));

	ll pg = -1, pp = -1, sl = 0;
	vll us(n);
	forn(i, n) {
		if (us[i])
			continue;
		if (pg != a[i]) {
			pg = a[i];
			sl = i; // ?
		}
		while (sl < n && (a[sl] == pg || us[sl]))
			++sl;

		if (pp == a[i]) {
			ans.push_back(sl);
			us[sl] = 1;
		}

		ans.push_back(i);
		us[i] = 1;
	}

	return invp(ans);
}

#ifdef _LOCAL
void tests() {
	mt19937 mt;

	ll t;
	cin >> t;

	while (t--) {

	}
}
#endif // _LOCAL


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

#ifdef _LOCAL
	while (1)
#endif // _LOCAL
	{
		ll t = 1;
		//cin >> t;
		while (t--) {
			ll n, m;
			cin >> n >> m;
			vll a(n);
			vpll b(m);
			cin >> a;
			for (auto& [o, x] : b) {
				cin >> o >> x;
				--x;
			}

			vll ans = ask(a);
			for (auto& [o, x] : b) {
				if (o == 1) {
					swap(a[x], a[x + 1]);
					ans = ask(a);
				}
				else {
					cout << ans[x] + 1 << '\n';
				}
			}

			cout << endl;
		}
	};
}
