#include <bits/stdc++.h>
using namespace std;
struct TRee
{
	int l,r;
	int sum,val,lv,rv;
}t[4000005];
int n,q,a[1000005];
void push_up(int p)
{
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].val=max(t[p*2].val,max(t[p*2+1].val,t[p*2].rv+t[p*2+1].lv));
	t[p].lv=max(t[p*2].lv,t[p*2+1].lv+t[p*2].sum);
	t[p].rv=max(t[p*2+1].rv,t[p*2].rv+t[p*2].sum);
}
void buildSGM(int p,int l,int r)
{
	t[p].l=l; t[p].r=r;
	if (l==r)
	{
		t[p].sum=a[l];
		t[p].val=a[l];
		t[p].lv=a[l];
		t[p].rv=a[l];
		return ;
	}
	int mid =(l+r)/2;
	buildSGM(p*2,l,mid);
	buildSGM(p*2+1,mid+1,r);
	push_up(p);
}
void change(int p,int x,int v)
{
	if (t[p].l==t[p].r) 
	{
		t[p].sum=v;
		t[p].val=v;
		t[p].lv=v;
		t[p].rv=v;
		return;
	}
	int mid=(t[p].l+t[p].r)/2;
	if (x<=mid) change(p*2,x,v);
	else change(p*2+1,x,v);
    push_up(p);
}
TRee ask(int p,int l,int r)
{
	if (l<=t[p].l&&r>=t[p].r)
	{
		return t[p];
	}
	int mid=(t[p].l+t[p].r)/2;
	TRee vall;
	if (l<=mid&&r>mid)
	{
		TRee aa=ask(p*2,l,r);
		TRee bb=ask(p*2+1,l,r);
		vall.sum=aa.sum+bb.sum;
		vall.val=max(aa.val,max(bb.val,aa.rv+bb.lv));
		vall.lv=max(aa.lv,bb.lv+aa.sum);
		vall.rv=max(bb.rv,aa.rv+aa.sum);
		return vall;
	}
	if (l<=mid)
	{
		return ask(p*2,l,r);
	}
	if (r>mid)
	{
		return ask(p*2+1,l,r);
	}
}
int main()
{
	cin>>n>>q;
	for (int i=1;i<=n;i++) cin>>a[i];
	buildSGM(1,1,n);
	for (int i=1;i<=q;i++)
	{
		int xx;
		cin>>xx;
		if (xx==1)
		{
			int ss,tt;
			cin>>ss>>tt; 
			if (ss>tt) swap(ss,tt); 
			TRee xxx=ask(1,ss,tt);
			cout<<xxx.val<<'\n';
		}
		if (xx==2)
		{
			int pp,ss;
			cin>>pp>>ss;
			change(1,pp,ss);
		}
	}
	return 0; 
}