#include<bits/stdc++.h>
#include<stack>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=x*10+(c^48);
		c=getchar();
	}
	return x*f;
}
#define re register

int n,m;
const int inf=0x3f3f3f3f;
const int N=5e5+10;
int a[N];

namespace seg
{
#define ls (rt*2)
#define rs (rt*2+1)
#define mid ((l+r)>>1)
	struct node
	{
		int all_max,sum,left_max,right_max;
	} t[N*4];
	inline void mat(int rt)
	{
		t[rt].sum = t[rs].sum + t[ls].sum;
		t[rt].left_max = max( t[ls].left_max , t[ls].all_max+t[rs].left_max );
		t[rt].right_max = max( t[rs].right_max , t[rs].all_max+t[ls].right_max );
		t[rt].all_max = max( max(t[ls].all_max,t[rs].all_max) , t[rs].left_max + t[ls].right_max );
	}
	inline void build(int rt,int l,int r)
	{
		if(l==r)
		{
			t[rt].all_max=a[l];
			t[rt].left_max=a[l];
			t[rt].right_max=a[l];
			t[rt].sum=a[l];
			return ;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		mat(rt);
	}
	inline void modify(int rt,int l,int r,int p,int v)
	{
		if(l==p && r==p)
		{
			t[rt].all_max=v;
			t[rt].left_max=v;
			t[rt].right_max=v;
			t[rt].sum=v;
			return ;
		}
		if(p<=mid)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		mat(rt);
	}
	inline node query(int rt,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
		{
			return t[rt];
		}
		node ans,al,ar;
		ans.sum=0;
		if(R<=mid) ans=query(ls,l,mid,L,R);
		if(L>mid)  ans=query(rs,mid+1,r,L,R);
		if(L<=mid&&mid<R)
		{
			al=query(ls,l,mid,L,R);
			ar=query(rs,mid+1,r,L,R);
			ans.sum=al.sum+ar.sum;
			ans.left_max=max( al.left_max , al.all_max+ar.left_max  );
			ans.right_max=max( ar.right_max , ar.all_max+al.right_max );
			ans.all_max=max( max(al.all_max,ar.all_max),al.right_max+ar.left_max  );
		}
		return ans;
	}
}
int main()
{
	freopen("P4513_2.in","r",stdin);
	freopen("ans.out","w",stdout);
	n=read();
	m=read();
	for(int i=1; i<=n; i++) a[i]=read();
	seg::build(1,1,n);
	while(m--)
	{
		int opt=read();
		if(opt==1)
		{
			int l=read(),r=read();
			if(l>r)swap(l,r);
			seg::node ans=seg::query(1,1,n,l,r);
			cout<< ans.all_max <<endl;
		}
		else
		{
			int p=read(),s=read();
			seg::modify(1,1,n,p,s);
		}
	}
}