#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef long long int ll;
struct node
{
	ll l,r;
	ll mal,mar;
	ll sum;
	ll ans;
}c[maxn<<2];
ll a[maxn];
void pushup(int x)
{
	c[x].mal=max(c[x<<1].mal,c[x<<1].sum+c[x<<1|1].mal);
	c[x].mar=max(c[x<<1|1].mar,c[x<<1|1].sum+c[x<<1].mar);
	c[x].sum=c[x<<1].sum+c[x<<1|1].sum;
	c[x].ans=max(max(c[x<<1].ans,c[x<<1|1].ans),c[x<<1].mar+c[x<<1|1].mal);
}
void build(int l,int r,int x)
{
	if(l==r)
	{
		c[x].l=l,c[x].r=r;
		c[x].mal=c[x].mar=c[x].ans=a[l]=c[x].sum=a[l];
		return;
	}
	c[x].l=l;c[x].r=r;
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	pushup(x);
	return;
}
void modify(int x,int pos,int k)
{

	if(c[x].l==c[x].r)
	{
		c[x].sum=c[x].mal=c[x].mar=c[x].ans=k;
		return;
	}
	ll mid=(c[x].l+c[x].r)>>1;
	if(mid>=pos)
		modify(x<<1,pos,k);
	else
		modify(x<<1|1,pos,k);
	pushup(x);
	return;
}
node query(int x,int l,int r)
{
	if(c[x].l>=l&&c[x].r<=r)
		return c[x];
	ll mid=(c[x].l+c[x].r)>>1;
	if(mid>=l)
		return query(x<<1,l,r);
	else if(mid+1<=r)
		return query(x<<1|1,l,r);
	node ls=query(x<<1,l,r),rs=query(x<<1|1,l,r),ans;
	ans.l=c[x].l;ans.r=c[x].r;
	ans.mal=max(ls.mal,ls.sum+rs.mal);
	ans.mar=max(rs.mar,rs.sum+ls.mar);
	ans.sum=ls.sum+rs.sum;
	ans.ans=max(max(ls.ans,rs.ans),ls.mar+rs.mal);
	return ans;
}
int main()
{
//	freopen("P4513_2.in","r",stdin);
//	freopen("P4513.out","w",stdout); 
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		int op,x,y;
		scanf("%d",&op);
		if(op==2)
		{
			scanf("%d%d",&x,&y);
			modify(1,x,y);
		}
		else
		{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(1,min(x,y),max(x,y)).ans);
		}
	}
	return 0;
}