#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 500005
#define N   2000005
#define inf 0x3f3f3f3f

/*
维护选 1,2,3 个的最后一个最小值 记为 A,B,C (A<B<C)
if(x<=A) A=x
else if(x<=B) B=x
else if(x<=C) C=x
else find the ans
seg-beats 强行维护 
c<x 的直接递归到叶子；c>=x的所有c变成x 

pair
<a.fi,a.se>
<b[1].fi,b[1].se> (all)
<b[0].fi,b[0].se> (a次小)
<c[1/0][1/0]> (all/a次小；all/b次小)
c is min_c
*/

int n,m,k,res[maxn],nowt;
vector<pii>q[maxn];
vi in[maxn];

pii a[N],b[N][2];
int c[N][2][2];
int ta[N],tb[N][2],tc[N][2][2];
bool ban[N];
pii operator +(pii a,pii b){
	pii c;
	c.fi=max(a.fi,b.fi);
	c.se=max(a.fi==c.fi?a.se:a.fi,b.fi==c.fi?b.se:b.fi);
	return c;
}
void up(int p)
{
	int ls=p<<1,rs=p<<1|1;
	ban[p]=ban[p<<1]&&ban[p<<1|1];
	if(!ban[ls])a[p]=a[ls];
	else a[p]=mkp(-inf,-inf);
	if(!ban[rs])a[p]=a[p]+a[rs];
	For(i,0,1){
		b[p][i]=mkp(-inf,-inf);
		for(int t:{ls,rs})if(!ban[t])b[p][i]=b[p][i]+b[t][i||(a[p].fi>a[t].fi)];
	}
	For(i,0,1)
		For(j,0,1){
			c[p][i][j]=inf;
			for(int t:{ls,rs})if(!ban[t]){
				int ia=i||(a[p].fi>a[t].fi);
				int jb=j||(b[p][i].fi>b[t][ia].fi);
				c[p][i][j]=min(c[p][i][j],c[t][ia][jb]);
			}
		}
}
// a,b tag : change max
// c tag : change all 
void down(int p)
{
	int ls=p<<1,rs=p<<1|1;
	if(ta[p]!=-inf){
		if(!ban[ls]&&a[ls].fi>=a[rs].fi)a[ls].fi=ta[ls]=ta[p];
		if(!ban[rs]&&a[rs].fi>=a[ls].fi)a[rs].fi=ta[rs]=ta[p];
		ta[p]=-inf;
	}
	For(i,0,1)
		if(tb[p][i]!=-inf){
			for(int t:{ls,rs})if(!ban[t]){
				int ia=i||(a[p].fi>a[t].fi);
				if(b[t][ia].fi>=b[t^1][i||(a[p].fi>a[t^1].fi)].fi)
					b[t][ia].fi=tb[t][ia]=tb[p][i];
			}
			tb[p][i]=-inf;
		}
	For(i,0,1)
		For(j,0,1)
			if(tc[p][i][j]!=-inf){
				for(int t:{ls,rs})if(!ban[t]){
					int ia=i||(a[p].fi>a[t].fi);
					int jb=j||(b[p][i].fi>b[t][ia].fi);
					c[t][ia][jb]=tc[t][ia][jb]=tc[p][i][j];
				}
				tc[p][i][j]=-inf;
			}
}

int nl,nr,x;
void mdfC(int p,int l,int r,int i,int j)
{
//	cout<<"mdfC "<<l<<" "<<r<<" "<<i<<" "<<j<<endl;
	if(ban[p])return;
	if(x<=c[p][i][j]){
		c[p][i][j]=tc[p][i][j]=x;
		return;
	}
	if(l==r){
//		cout<<"pop "<<l<<endl;
		res[l]=nowt;
		a[p].fi=-inf+1;
		ban[p]=1;
		return;
	}
	int mid=l+r>>1,ia,jb; down(p);
	ia=i||(a[p].fi>a[p<<1].fi);
	jb=j||(b[p][i].fi>b[p<<1][ia].fi);
	mdfC(p<<1,l,mid,ia,jb);
	ia=i||(a[p].fi>a[p<<1|1].fi);
	jb=j||(b[p][i].fi>b[p<<1|1][ia].fi);
	mdfC(p<<1|1,mid+1,r,ia,jb); up(p);
}
void mdfB(int p,int l,int r,int i)
{
//	cout<<"mdfB "<<l<<" "<<r<<' '<<i<<endl;
	if(ban[p])return;
	if(x>b[p][i].fi)return mdfC(p,l,r,i,1);
	else if(x>b[p][i].se)return b[p][i].fi=tb[p][i]=x,mdfC(p,l,r,i,0);
	int mid=l+r>>1; down(p);
	mdfB(p<<1,l,mid,i||(a[p].fi>a[p<<1].fi));
	mdfB(p<<1|1,mid+1,r,i||(a[p].fi>a[p<<1|1].fi)); up(p);
}
void mdfA(int p,int l,int r)
{
//	if(p==1)cout<<"mdfA "<<nl<<" "<<nr<<" "<<x<<endl;
	if(ban[p])return;
	if(l>=nl&&r<=nr){
		if(x>a[p].fi)return mdfB(p,l,r,1);
		else if(x>a[p].se)return a[p].fi=ta[p]=x,mdfB(p,l,r,0);
	}
	int mid=l+r>>1; down(p);
	if(nl<=mid)mdfA(p<<1,l,mid);
	if(nr>mid)mdfA(p<<1|1,mid+1,r); up(p);
}
void build(int p,int l,int r)
{
	ta[p]=-inf;
	For(i,0,1){tb[p][i]=-inf;For(j,0,1)tc[p][i][j]=-inf;}
	if(l==r){
		a[p].fi=a[p].se=-inf;ban[p]=1;
		For(i,0,1){b[p][i].fi=b[p][i].se=-inf;For(j,0,1)c[p][i][j]=inf+1;}
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r),up(p);
}
void add(int p,int l,int r,int x)
{
	if(l==r){
		a[p].fi=inf,a[p].se=-inf;
		b[p][1].fi=inf;
		c[p][1][1]=inf;
		ban[p]=0;
		return;
	}
	int mid=l+r>>1; down(p);
	x<=mid?add(p<<1,l,mid,x):add(p<<1|1,mid+1,r,x); up(p);
}

signed main()
{
	n=read(),m=read();
	For(i,1,n)q[i].pb(mkp(read(),0));
	For(i,1,m){
		int o=read();
		if(o==2)++k,in[read()].pb(k),res[k]=-1;
		else{
			int x=read(),y=read();
			q[x].pb(mkp(y,k));
		}
	}
//	for(auto t:q[3])cout<<t.fi<<" "<<t.se<<"\n";
	build(1,1,k);
	For(i,1,n){
//		cout<<"wk "<<i<<endl;
		nowt=i;
		for(auto t:in[i])add(1,1,k,t);
		int siz=q[i].size();
//		puts("qaq");
		For(j,0,siz-1){
			nl=q[i][j].se+1,nr=(j<siz-1?q[i][j+1].se:k),x=q[i][j].fi;
			if(nl<=nr)mdfA(1,1,k);
		}
	}
	For(i,1,k)printf("%d\n",res[i]);
	return 0;
}
/*
11 7
1 2 3 4 5 10 9 8 7 6 8
2 1
1 3 2
2 1
1 1 2
2 1
2 5
*/