#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arb,v;

int m,n,i,c,x,y,mx;

void nodmax(int nod,int L,int R,int a,int b)
{
	int M;

	if(a<=L&&R<=b)
	{
		if(mx<arb[nod]) mx=arb[nod];
	}
	else
	{
		M=(L+R)/2;
		if(a<=M) nodmax(2*nod,L,M,a,b);
		if(b>M) nodmax(2*nod+1,M+1,R,a,b);
	}
}

int main()
{
	freopen("arbint.in","r",stdin);
	freopen("arbint.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		arb.push_back(x);
		v.push_back(x);
	}
	make_heap(arb.begin(),arb.end());

	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&c,&x,&y);
		if(c==1)
		{
			x--;
			remove(arb.begin(),arb.end(),v[x]);
			arb.pop_back();
			arb.push_back(y);
			push_heap(arb.begin(),arb.end());
			v[x]=y;
		}
		else
		{
			mx=0;
			nodmax(0,0,99999,x,y);
			printf("%d\n",mx);
		}
	}

	return 0;
}