#include<fstream>
#include<algorithm>
#define N 100100
#define FOR(a,b,c) for(register int a=b;a<=c;++a)
#define ROF(a,b,c) for(register int a=b;a>=c;--a)
using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
int n,a,b,tip,m,x;
struct Tr
{
	Tr *l,*r;
	int key,val,ma,pr;
	Tr(){}
	Tr(int _key,int _pr,int _val)
	{
		key=_key;
		pr=_pr;
		ma=val=_val;
		l=r=NULL;
	}
};
#define T Tr*
T R;
int ma(T t)
{
	if(!t)
		return 0;
	return t->ma;
}
void upd(T &t)
{
	if(!t)
		return;
	t->ma=max(t->val,max(ma(t->l),ma(t->r)));
}
void split(T t,T &l,T &r,int k)
{
	if(!t)
		l=r=NULL;
	else
	if(k<=t->key)
		split(t->l,l,t->l,k),r=t;
	else
		split(t->r,t->r,r,k),l=t;
	upd(t);
}
void merge(T &t,T l,T r)
{
	if(!l||!r)
		t=l?l:r;
	else
	if(l->pr > r->pr)
		merge(l->r,l->r,r),t=l;
	else
		merge(r->l,l,r->l),t=r;
	upd(t);
}
void insert(T &t,T it)
{
	if(!t)
		t=it;
	else
	if(it->pr > t->pr)
		split(t,it->l,it->r,it->key),t=it;
	else
		insert(it->key > t->key ? t->r : t-> l,it);
	upd(t);
}
void erase(T &t,int k)
{
	if(t->key==k)
		merge(t,t->l,t->r);
	else
		erase(k > t->key ? t->r : t->l,k);
	upd(t);
}
void query(int l,int r)
{
	Tr *t1,*t2,*t3;
	split(R,t1,t2,l);
	split(t2,t2,t3,r+1);
	g<<t2->ma<<"\n";
	merge(R,t1,t2);
	merge(R,R,t3);
}
int main ()
{
	f>>n>>m;
	FOR(i,1,n)
	{
		f>>x;
		T t=new Tr(i,rand()+1,x);
		insert(R,t);
	}
	FOR(i,1,m)
	{
		f>>tip;
		if(!tip)
		{
			f>>a>>b;
			query(a,b);
		}
		else
		{
			f>>a>>b;
			erase(R,a);
			T t=new Tr(a,rand()+1,b);
			insert(R,t);
		}
	}
	return 0;
}
//Look at me!Look at me!The monster inside me has grown this big!