#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int v[18001];

inline int query(int nod,int s,int d,int l,int r)
{
 	if ((d<l)||(s>r)) return 0;
	if ((l<=s)&&(d<=r)) return v[nod];
	int a,b;
	a=query(2*nod,s,(s+d)/2,l,r);
	b=query(2*nod+1,(s+d)/2+1,d,l,r);
	if (a>b)
		return a;
	return b;
}

int main()
{
	int i=1,j,x=2,n,m,a,b,c;
	freopen("arbint.in","r",stdin);
	freopen("arbint.out","w",stdout);
	scanf("%d%d",&n,&m);
	do
	{
		x*=2;
	}
	while (n>x);
	for (i=x;i<x+n;i++) scanf("%d",&v[i]);
	for (i=x-1;i>0;i--) v[i]=(v[2*i]+v[2*i+1]+abs(v[2*i]-v[2*i+1]))/2;
	for (i=1;i<m+1;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		if (a==1)
		{
			v[x-1+b]=c;
			for (j=(x+b-1)/2;j>0;j=j/2)
			{
				v[j]=v[2*j];
				if (v[2*j+1]>v[j]) v[j]=v[2*j+1];
			}
		}
		else printf("%d\n",query(1,1,x,b,c));
	}
	return 0;
}