#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N];
struct tree{
	int ml,mr,ans,sum;
}t[4*N];
void push_in(int u)
{
	t[u].sum=t[2*u].sum+t[2*u+1].sum;
	t[u].ml=max(t[u*2].ml,t[u*2].sum+t[u*2+1].ml);
	t[u].mr=max(t[u*2+1].mr,t[u*2].mr+t[2*u+1].sum);
	t[u].ans=max(max(t[u*2].ans,t[u*2+1].ans),t[u*2].mr+t[u*2+1].ml);
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		t[u].ml=t[u].mr=t[u].sum=t[u].ans=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	push_in(u);
}
tree query(int u,int l,int r,int a,int b)
{
	if(l>=a&&r<=b)
	{
		return t[u];
	}
	int mid=(l+r)/2;
	if(b<=mid)
	{
		return query(u*2,l,mid,a,b);
	}
	else if(a>mid)
	{
		return query(u*2+1,mid+1,r,a,b);
	}
	else
	{
		tree s,x=query(u*2,l,mid,a,b),y=query(u*2+1,mid+1,r,a,b);
		s.ml=max(x.ml,x.sum+y.ml);
		s.mr=max(x.mr,x.mr+y.sum);
		s.ans=max(max(x.ans,y.ans),x.mr+y.ml);
		return s;
	}
}
void update(int u,int l,int r,int a,int b)
{
	if(l==r)
	{
		t[u].ml=t[u].mr=t[u].sum=t[u].ans=b;
		return ;
	}
	int mid=(l+r)/2;
	if(a<=mid)
	{
		update(u*2,l,mid,a,b);
	}
	else
	{
		update(u*2+1,mid+1,r,a,b);
	}
	push_in(u);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int a,b,op;
		cin>>op>>a>>b;
		if(op==1)
		{
			if(a>b)
			{
				swap(a,b);
			}
			cout<<query(1,1,n,a,b).ans<<endl;
		}
		else
		{
			update(1,1,n,a,b);
		}
	}
	return 0;
}