#include<iostream>
using namespace std;
struct tree
{
	int l,r;
	long long dat,sum,lmax,rmax;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define sum(x) t[x].sum
	#define lmax(x) t[x].lmax
	#define rmax(x) t[x].rmax
	#define dat(x) t[x].dat
}t[2000005];
int n,m,a[500005];
void build(int p,int l,int r)
{
	l(p)=l,r(p)=r;
	if(l==r)
	{
		sum(p)=a[l];
		lmax(p)=a[l];
		rmax(p)=a[l];
		dat(p)=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	sum(p)=sum(p*2)+sum(p*2+1);
	lmax(p)=max(lmax(p*2),sum(p*2)+lmax(p*2+1));
	rmax(p)=max(rmax(p*2+1),sum(p*2+1)+rmax(p*2));
	dat(p)=max(dat(p*2),max(dat(p*2+1),rmax(p*2)+lmax(p*2+1)));
	return;
}
void change(int p,int x,int d)
{
	if(l(p)==r(p))
	{
		sum(p)=d;
		lmax(p)=d;
		rmax(p)=d;
		dat(p)=d;
		return;		
	}
	int mid=(l(p)+r(p))>>1;
	if(x<=mid)change(p*2,x,d);
	else change(p*2+1,x,d);
	sum(p)=sum(p*2)+sum(p*2+1);
	lmax(p)=max(lmax(p*2),sum(p*2)+lmax(p*2+1));
	rmax(p)=max(rmax(p*2+1),sum(p*2+1)+rmax(p*2));
	dat(p)=max(dat(p*2),max(dat(p*2+1),rmax(p*2)+lmax(p*2+1)));
	return;	
}
long long ask(int p,int l,int r)
{
	if(l<=l(p)&&r>=r(p))
	{
		return dat(p); 
	}
	int mid=(l(p)+r(p))>>1;
	long long Max=-500000005;
	if(l<=mid)Max=max(Max,ask(p*2,l,r));
	if(r>mid)Max=max(Max,ask(p*2+1,l,r));
	return Max;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	while(m--)
	{
		int flag;
		scanf("%d",&flag);
		if(flag==1)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			if(l>r)swap(l,r);
			printf("%lld\n",ask(1,l,r));
		}
		else
		{
			int x,d;
			scanf("%d%d",&x,&d);
			change(1,x,d);
		}
	}
	return 0;
}