#include <iostream>
#include <cstdio>
using namespace std;
const int p = 1e6;
int a[p], co[p];
void Sort(int n, int flag)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j >= 2; j--)
			if (co[j] < co[j - 1]) 
			{
				swap(co[j], co[j - 1]);
				if(flag == co[j])
					flag -= 1;
				else if(flag == co[j - 1])
					flag += 1;
			}
		/*for(int u = 1; u <= n; u++)
			printf("%d ", co[u]);
		printf("\n");*/
	}
}
void Copy(int n)
{
	for(int i = 1; i <= n; i++)
		co[i] = 0;
	for(int i = 1; i <= n; i++)
		co[i] = a[i];
}
int main()
{
	int n, q;
	int src;
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	//Sort(n, src);
	//
	for(int i = 1; i <= q; i++)
	{
		int d, b, c;
		scanf("%d", &d);
		if(d == 1)
		{
			scanf("%d &d", &b, &c);
			a[b] = c;
		}
		else
		{
			scanf("%d", &b);
			Copy(n);
			Sort(n, b);
			printf("%d\n", b);
		}
	}
	return 0;
}