QWQ

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m,a[8000000];
ll op,x,y;
struct qwe{
	ll l,r;
	ll l1,r1,sum,ma;
}t[8000000];

void pu(ll p)
{
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].l1=max(t[p*2].l1,t[p*2].sum+t[p*2+1].l1);
	t[p].r1=max(t[p*2+1].r1,t[p*2+1].sum+t[p*2].r1);
	t[p].ma=max(t[p*2].ma,max(t[p*2+1].ma,t[p*2].r1+t[p*2+1].l1));
}

void build(ll p,ll x,ll y)
{
	t[p].l=x;
	t[p].r=y;
	if(x==y)
	{
		t[p].l1=t[p].r1=t[p].sum=t[p].ma=a[x];
		return;
	}
	
	build(p*2,x,(x+y)/2);
	build(p*2+1,(x+y)/2+1,y);
	pu(p);
}

void insert(ll p,ll x,ll y)
{
	if(t[p].l==t[p].r)
	{
		t[p].l1=t[p].r1=t[p].ma=t[p].sum=y;
		return;
	}
	ll mm=(t[p].l+t[p].r)/2;
	if(x<=mm)insert(p*2,x,y);
	else insert(p*2+1,x,y);
	pu(p);
}

qwe ask(ll p,ll x,ll y)
{
	if(x<=t[p].l&&t[p].r<=y)return t[p];
	ll mm=(t[p].l+t[p].r)/2;
	
	if(y<=mm)return ask(p*2,x,y);
	else 
	{
		if(x>mm)return ask(p*2+1,x,y);
		else 
		{
			qwe xx,tmp1=ask(p*2,x,y),tmp2=ask(p*2+1,x,y);
			xx.l1=max(tmp1.l1,tmp1.sum+tmp2.l1);
			xx.r1=max(tmp2.r1,tmp2.sum+tmp1.r1);
			xx.ma=max(tmp1.ma,max(tmp2.ma,tmp1.r1+tmp2.l1));
			return xx;
		}
	}
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);
	
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==1)x=min(x,y),y=max(x,y),printf("%lld\n",ask(1,x,y).ma);
		else insert(1,x,y);
	}
}