#include<fstream.h>

int lg, n, v[100005],aib[100006],ord[100005],sol[100005];

int querry(int l , int r)
{
	int x,y=0;
	while (r>=l)
	{
		x=r-(r&(-r));
		if (x<l)
		{
			x=r-1;
			if (v[y]<v[r])
				y=r;
			
		}
		else
			if (v[y]<v[aib[r]])
				y=aib[r];
		r=x;
	}
	return y;
}

int pozitie(int nr)
{
	int s,x,i;
	x=lg;s=0;
	for (;x;x>>=1)
		if (s+x<=n && ord[s+x]<nr)
			nr-=ord[s+x],s+=x;
	return s+1;
}

void updateord(int i, int s)
{
	for(;i<=n;i+=i&(-i))
		ord[i]+=s;
}

void updatemax (int poz)
{
	int x,y,z=poz;
	x=poz;
	for (;x<=n;x+= (x & (-x)) )
		if (aib[x]==z)
		{
			y=querry(x- (x&(-x))+1, x-1);
			if (v[y]>v[x])
				aib[x]=y;
			else
				aib[x]=x;
		}
		else
			if (v[z]>v[aib[x]])
				aib[x]=z;
			else 
				break;
}

int main()
{
	int i,m,x,y,l,r,poz,op;
	ifstream f("arbint.in");
	f>>n>>m;
	
	for (lg=1<<20;log>n;log>>=1);
	
	for (i=1;i<=n;i++)
	{
		f>>v[i];
		updatemax(i);
		//updateord(i,+1);
	}
	
	ofstream g("arbint.out");
	for(i=1;i<=m;i++)
	{
		f>>op;
		f>>x>>y;
		if (op==0)
			g<<v[querry(x,y)]<<'\n';
		else 
		{
			v[x]=y;
			updatemax(x);
		}
			
		//l=pozitie(x);
		//r=pozitie(y);
		//poz=querry(l,r);
		//sol[poz]++;
		//updateord(poz,-1);
		//v[poz]=-1;
		//updatemax(poz);
	}
//
	//for (i=1;i<=n;i++)
		//if (!sol[i])
			//g<<v[i]<<'\n';
	f.close();
	g.close();
	return 0;
}