#include<bits/stdc++.h>
#define rm (x*2+1)
#define lm (x*2)
#define mid ((l+r)/2)
#define ll long long
using namespace std;
const ll N=3e6+5;
ll sum[N],n,m,a[N],rl[N],lr[N],ans[N];
void update(ll x)
{
	sum[x]=sum[lm]+sum[rm];
	rl[x]=max(rl[rm],sum[rm]+rl[lm]);
	lr[x]=max(lr[lm],sum[lm]+lr[rm]);
	ans[x]=max(max(ans[lm],ans[rm]),rl[lm]+lr[rm]);
}
void build(ll x,ll l,ll r)
{
	if(l==r)
	{
		sum[x]=rl[x]=lr[x]=ans[x]=a[l];
		return ;
	}
	build(lm,l,mid);
	build(rm,mid+1,r);
	update(x);
}
void add(ll x,ll l,ll r,ll k,ll kk)
{
	if(l==r)
	{
		a[l]=sum[x]=rl[x]=lr[x]=ans[x]=kk;
		return ;
	}
	if(k>mid) add(rm,mid+1,r,k,kk);
	else add(lm,l,mid,k,kk);
	update(x);
}
ll fans[N],cnt;
void find(ll x,ll l,ll r,ll L,ll R)
{
	if(l>=L&&r<=R) 
	{
		fans[++cnt]=x;
		return ;
	}
	if(L<=mid) find(lm,l,mid,L,mid);
	if(R>mid) find(rm,mid+1,r,mid+1,R);
}
int main()
{
//	cout<<"dongruoqi\n";
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--)
	{
		ll p;
		cin>>p;
		if(p==1)
		{
			ll xx,yy;
			cin>>xx>>yy;
			if(xx>yy) swap(xx,yy);
			cnt=0;
			find(1,1,n,xx,yy);
			ll summ=sum[fans[1]],rll=rl[fans[1]],lrr=lr[fans[1]],anss=ans[fans[1]];
			for(ll i=2;i<=cnt;i++)
			{
				anss=max(anss,max(ans[fans[i]],rll+lr[fans[i]]));
				rll=max(rl[fans[i]],rll+sum[fans[i]]);
				lrr=max(lrr,summ+lr[fans[i]]);
				summ=summ+sum[fans[i]];
			}
			cout<<anss<<"\n";
		}
		else
		{
			ll pp,s;
			cin>>pp>>s;
			add(1,1,n,pp,s);
		}
	}
	return 0;
}