#include <bits/stdc++.h>

using namespace std;

struct treap;
struct node;

typedef treap* pt;
typedef node* pn;

struct node
{
	int v; //position
	int o; //value
	int m; //max value of subtree
	
	int lr,rr; //range of subtree
	int p; //prob
	
	pn l,r;
	
	node(int v, int o) : v(v),o(o),p(rand())	{}
	~node() { delete l; delete r;}
	
	void gg() //recalculate values
	{
		lr = rr = v;
		m=o;
		if (l) lr = min(lr,l->lr), rr = max(rr, l->rr), m = max(m,l->m);
		if (r) lr = min(lr,r->lr), rr = max(rr, r->rr), m = max(m,r->m);
	}	
};

pn merge(pn l, pn r)
{
	if (!l || !r) return l?l:r; //check empty
	if (l->p < r->p)
	{
		l->r = merge(l->r,r);
		l->gg();
		return l;
	} else 
	{
		r->l = merge(l,r->l);
		r->gg();
		return r;
	}
}

void split(pn v, int x, pn &l, pn &r)
{
	l=r=0;
	if (!v) return;
	if (v->v < x)
	{
		split(v->r,x,v->r,r);
		l=v;		
	} else
	{
		split(v->l,x,l,v->l);
		r = v;
	}	
	v->gg();
}

struct treap
{
	pn root;
	
	treap() : root(0) {}
	
	~treap() { delete root;	}	
	
	void erase(int v)
	{
		pn l,m,r;
		split(root,v,l,m);
		split(m,v+1,m,r);
		if (m) delete m;
		root = merge(l,r);
	}
	
	void insert(int v, int x)
	{
		erase(v);
		pn l,r;
		split(root,v,l,r);
		root = merge(merge(l,new node(v,x)),r);
	}
	
	void query(pn t, int l, int r, int &ans)
	{
		if (!t) return ;
		if (t->rr < l) return ;
		if (t->lr > r) return ;
		if (t->lr >= l && t->rr <=r) { ans = max(ans,t->m); return;}
		if (t->v >= l && t->v <=r) ans = max(ans,t->o);
		query(t->l, l, r, ans);
		query(t->r, l, r, ans);
	}
};

treap t;


int main()
{
	ifstream cin("arbint.in");
	ofstream cout("arbint.out");
	
	srand(time(0));
	
	int n,m;
	cin>>n>>m;
	for (int i=0; i<n; i++)
	{	int x; cin>>x; t.insert(i,x); }
	
	for (int i=0; i<m; i++)
	{	int x,y,z; cin>>x>>y>>z; if (x) t.insert(y-1,z); else t.query(t.root, y-1,z-1, x), cout<<x<<'\n'; }
	
    return 0;
}