#include<fstream>
#define inf 1<<30
#define FOR(a,b,c) for(register int a=b;a<=c;++a)
#include<ctime>
#include<cstdlib>
using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
int n,x,m,tip,sol,st,dr,poz;
struct T
{
	T *lef,*rig;
	int lm,rm,po,val,pr,ma;
	T() {}
	T(int _po,int _pr,int _ma,T *_lef,T *_rig,int _val)
	{
		pr=_pr;
		lm=rm=po=_po;
		ma=_ma;
		lef=_lef;
		rig=_rig;
		val=_val;
	}
}*R, *nil;
void init()
{
	srand(time(0));
	R=nil=new T(inf,0,0,NULL,NULL,0);
	nil->lef=nil->rig=nil;
}
void upd(T* &nod)
{
	nod->ma=max(nod->val,max(nod->lef->ma,nod->rig->ma));
	nod->lm=nod->rm=nod->po;
	if(nod->lef!=nil)
		nod->lm=min(nod->lm,nod->lef->lm);
	if(nod->rig!=nil)
		nod->rm=max(nod->rm,nod->rig->rm);
}
void rlef(T* &nod)
{
	T *aux=nod->rig;
	nod->rig=aux->lef;
	aux->lef=nod;
	nod=aux;
	
	upd(nod->lef);
	upd(nod);
}
void rrig(T* &nod)
{
	T *aux=nod->lef;
	nod->lef=aux->rig;
	aux->rig=nod;
	nod=aux;
	
	upd(nod->rig);
	upd(nod);
}
void balance(T* &nod)
{
	if(nod->lef->pr > nod->pr)
		rrig(nod);
	if(nod->rig->pr > nod->pr)
		rlef(nod);
}
void insert(T* &nod,int po,int pr,int ma)
{
	if(nod==nil)
	{
		nod=new T(po,pr,ma,nil,nil,ma);
		return ;
	}
	if(po<nod->po)
		insert(nod->lef,po,pr,ma);
	else
		insert(nod->rig,po,pr,ma);
	upd(nod);
	balance(nod);
}
void delu(T* &nod,int po)
{
	if(nod==nil)
		return;
	if(nod->po==po)
	{
		if(nod->lef==nil&&nod->rig==nil)
		{
			delete(nod);
			nod=nil;
			return ;
		}
		if(nod->lef->pr > nod->rig->pr)
			rrig(nod),delu(nod->rig,po);
		else
			rlef(nod),delu(nod->lef,po);
	}
	else
	{
		if(po<nod->po)
			delu(nod->lef,po);
		else
			delu(nod->rig,po);
	}
	upd(nod);
}
void query(T* &nod,int st,int dr)
{
	if(nod->lm>=st&&nod->rm<=dr)
	{
		sol=max(sol,nod->ma);
		return ;
	}
	if(nod->po >= st && nod->po <= dr)
	sol=max(sol,nod->val);
	if(st<nod->po)
		query(nod->lef,st,dr);
	if(dr>nod->po)
		query(nod->rig,st,dr);
}
int main ()
{
	f>>n>>m;
	init();
	FOR(i,1,n)
	{
		f>>x;
		insert(R,i,rand()+1,x);
	}
	FOR(i,1,m)
	{
		f>>tip;
		if(!tip)
		{
			f>>st>>dr;
			sol=0;
			query(R,st,dr);
			g<<sol<<"\n";
		}
		else
		{
			f>>poz>>x;
			delu(R,poz);
			insert(R,poz,rand()+1,x);
		}
	}
	return 0;
}