$RT$

#include<bits/stdc++.h>
#define F(i,l,r) for(register int i=l;i<=r;i++)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define p_b push_back
#define m_p make_pair
#define il inline
using namespace std;
const int N=500005;
int n,m;
int k,u,v;
int a[N];
ll ans[N],pre[N],suff[N],sum[N];
int fr() {
	char ch=getchar();
	int num=0;
	int k=1;
	while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
	if(ch=='-') {
		k=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') {
		num=num*10+ch-'0';
		ch=getchar();
	}
	return num*k;
}
il int ls(int x) {return x<<1;}
il int rs(int x) {return x<<1|1;}
il void push_up(int p) {
	sum[p]=sum[ls(p)]+sum[rs(p)];
	pre[p]=max(pre[ls(p)],sum[ls(p)]+pre[rs(p)]);
	suff[p]=max(suff[rs(p)],sum[rs(p)]+suff[ls(p)]);
	ans[p]=max(max(ans[ls(p)],ans[rs(p)]),pre[rs(p)]+suff[ls(p)]);
}
il void build(int p,int l,int r) {
	if(l==r) {
		ans[p]=pre[p]=suff[p]=sum[p]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
il void upd(int pos,int p,int l,int r,int k) {
	if(l==r) {
		ans[p]=pre[p]=suff[p]=sum[p]=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) upd(pos,ls(p),l,mid,k);
	else upd(pos,rs(p),mid+1,r,k);
	push_up(p);
}
ll now,lst;
il void query(int ql,int qr,int p,int l,int r) {
	if(ql<=l&&qr>=r) {
		now=max(now,max(ans[p],lst+pre[p]));
		lst=max(suff[p],lst+sum[p]);
		return ;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) query(ql,qr,ls(p),l,mid);
	if(qr>mid) query(ql,qr,rs(p),mid+1,r);
}
int main() {
	n=fr(),m=fr();
	F(i,1,n) a[i]=fr();
	build(1,1,n);
	while(m--) {
		k=fr(),u=fr(),v=fr();
		if(u>v) swap(u,v);
		if(k==1) {
			now=lst=-1e15-7;
			query(u,v,1,1,n);
			printf("%lld\n",now);
		}
		else if(k==2) upd(u,1,1,n,v);
	}
	return 0;
}