#include<fstream.h>

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

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

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

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

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;lg>n;lg>>=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;
}