#include <bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
inline void in (int &x){
	int f=1;x=0;char c=getchar();
	while (c>'9'||c<'0'){if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
	x*=f;
}
int n,q,op,x,y,a[N];
struct Segment_Tree{
	int sum,ldat,rdat,dat;
}Tree[N<<2];
inline void push_up (int u){
	Tree[u].sum=Tree[u<<1].sum+Tree[u<<1|1].sum;
	Tree[u].ldat=max (Tree[u<<1].ldat,Tree[u<<1].sum+Tree[u<<1|1].ldat);
	Tree[u].rdat=max (Tree[u<<1|1].rdat,Tree[u<<1|1].sum+Tree[u<<1].rdat);
	Tree[u].dat=max (Tree[u<<1].rdat+Tree[u<<1].ldat,max (Tree[u<<1].dat,Tree[u<<1|1].dat));
}
inline void build (int l,int r,int u){
	if (l==r){Tree[u].sum=Tree[u].ldat=Tree[u].rdat=Tree[u].dat=a[l];return ;}
	int mid=l+r>>1;
	build (l,mid,u<<1);build (mid+1,r,u<<1|1);
	push_up (u);
}
inline void update (int x,int y,int l,int r,int u){
	if (l==r){Tree[u].dat=Tree[u].ldat=Tree[u].rdat=Tree[u].sum=y;return ;}
	int mid=l+r>>1;
	if (x<=mid) update (x,y,l,mid,u<<1);
	if (x>mid) update (x,y,mid+1,r,u<<1|1);
	push_up (u);
}
inline Segment_Tree query (int L,int R,int l,int r,int u){
	if (L<=l&&R>=r) return Tree[u];
	int mid=l+r>>1;
	if (mid<L) return query (L,R,mid+1,r,u<<1|1);
	if (mid>=R) return query (L,R,l,mid,u<<1);
	Segment_Tree ll,rr,Dat;
	ll=query (L,mid,l,mid,u<<1);
	rr=query (mid+1,R,mid+1,r,u<<1|1);
	Dat.sum=ll.sum+rr.sum;
	Dat.ldat=max (ll.ldat,ll.sum+rr.ldat);
	Dat.rdat=max (rr.rdat,rr.sum+ll.rdat);
	Dat.dat=max (ll.rdat+rr.ldat,max (ll.ldat,rr.rdat));
	return Dat;
}
signed main (){
	in (n);in (q);
	for (int i=1;i<=n;++i) in (a[i]);
	build (1,n,1);
	for (int i=1;i<=q;++i){
		in (op);in (x);in (y);
		if (op==1){if (x>y) swap (x,y);printf ("%lld\n",query (x,y,1,n,1).dat);}
		else update (x,y,1,n,1);
	}
	return 0;
}