#include <iostream>
#include <cstdio>
#define ls (s << 1)
#define rs (s << 1 | 1)
using namespace std;
struct node{
	int l,r,len,sum,mxl,mxr,mxsum;
}T[5010110];
int n,t,A[501111];
void pushup(node& fa,const node les,const node ris)
{
	fa.mxsum = max(les.mxr + ris.mxl,max(les.mxsum,ris.mxsum));
	fa.mxl = max(les.mxl,les.sum + ris.mxl);
	fa.mxr = max(ris.mxl,ris.sum + les.mxr);
	fa.sum = les.sum + ris.sum;
}
void build(int s,int l,int r)
{
	T[s] = (node){l,r,r - l + 1,0,-10000000,-10000000,-1000000};
	if(l == r)
	{
		T[s].sum = T[s].mxl = T[s].mxr = T[s].mxsum = A[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls,l,mid);
	build(rs,mid + 1,r);
	pushup(T[s],T[ls],T[rs]);
}
void modify(int s,int p,int x)
{
	if(T[s].l == T[s].r && T[s].r == p)
	{
		T[s].mxl = T[s].mxr = T[s].mxsum = T[s].sum = x;
		return;
	}
	int mid = (T[s].l + T[s].r) >> 1;
	if(p > mid)modify(rs,p,x);
	else modify(ls,p,x);
	pushup(T[s],T[ls],T[rs]);
}
node query(int s,int l,int r)
{
	if(T[s].l == l && T[s].r == r)return T[s];
	int mid = (T[s].l + T[s].r) >> 1;
	node ans;
	if(l > mid)ans = query(rs,l,r);
	else if(r <= mid)ans = query(ls,l,r);
	else
	{
		pushup(T[s],query(ls,l,mid),query(rs,mid + 1,r));
		ans = T[s];
	}
	return ans;
}
int main()
{
	cin>>n>>t;
	int i,j;
	for(i = 1;i <= n;i++)cin>>A[i];
	build(1,1,n);
	while(t--)
	{
		int op;cin>>op;
		if(op == 1)
		{
			int l,r;cin>>l>>r;
			if(l > r)swap(l,r);
			cout<<query(1,l,r).mxsum<<endl;
		}
		else
		{
			int p,x;cin>>p>>x;
			modify(1,p,x);
		}
	}
	return 0;
}