#include<bits/stdc++.h>
#define LL long long
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=4e5+5;
int a[N],n,m,op,x,y,z;
struct T{
	LL sum,lmx,rmx,mx,tag;
	int l,r,len,mid,numx,numl,numr;
}t[N*4],g;
int read(){
	int k=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') k=(k<<3)+(k<<1)+(c^48),c=getchar();
	return f*k;
}
T pushup(T &tr,T lc, T rc){
	tr.sum=lc.sum+rc.sum;
	if(lc.mx>rc.mx){tr.mx=lc.mx;tr.numx=lc.numx;}
	else{tr.mx=rc.mx;tr.numx=rc.numx;}
	if(lc.rmx+rc.lmx>tr.mx){tr.mx=lc.rmx+rc.lmx;tr.numx=lc.numr+rc.numl;}
	if(lc.lmx>lc.sum+rc.lmx){tr.lmx=lc.lmx;tr.numl=lc.numl;}
	else{tr.lmx=lc.sum+rc.lmx;tr.numl=lc.len+rc.numl;}
	if(rc.lmx>rc.sum+lc.rmx){tr.rmx=rc.rmx;tr.numr=rc.numr;}
	else{tr.rmx=rc.sum+lc.rmx;tr.numr=rc.len+lc.numr;}
	return tr;
}
void build(int u,int L,int R){
	t[u].l=L;t[u].r=R;t[u].len=R-L+1;t[u].mid=(L+R)>>1;t[u].tag=0;
	if(L==R){
		t[u].lmx=t[u].rmx=t[u].mx=t[u].sum=a[L];
		t[u].numl=t[u].numr=t[u].numx=1;
		return;
	}
	int M=(L+R)>>1;
	build(ls,L,M);
	build(rs,M+1,R);
	pushup(t[u],t[ls],t[rs]);
	return;
}
void pushdown(int u){
	if(!t[u].tag) return;
	t[ls].sum+=t[ls].len*t[u].tag;
	t[ls].mx+=t[ls].numx*t[u].tag;
	t[ls].lmx+=t[ls].numl*t[u].tag;
	t[ls].rmx+=t[ls].numr*t[u].tag;
	t[rs].sum+=t[rs].len*t[u].tag;
	t[rs].mx+=t[rs].numx*t[u].tag;
	t[rs].lmx+=t[rs].numl*t[u].tag;
	t[rs].rmx+=t[rs].numr*t[u].tag;
	t[ls].tag+=t[u].tag;
	t[rs].tag+=t[u].tag;
	t[u].tag=0;return;
}
T query(int u,int l,int r){
	if(l<=t[u].l&&t[u].r<=r)return t[u];
	pushdown(u);
	if(t[u].mid>=r) return query(ls,l,r);
	if(t[u].mid<l) return query(rs,l,r);
	return pushup(g,query(ls,l,r),query(rs,l,r));
}
void update(int u,int l,int r,int z){
	if(l<=t[u].l&&t[u].r<=r){
		t[u].sum+=t[u].len*z;
		t[u].mx+=t[u].numx*z;
		t[u].lmx+=t[u].numl*z;
		t[u].rmx+=t[u].numr*z;
		t[u].tag+=z;
		//printf("[%d,%d]:%d %d %d %d\n",t[u].l,t[u].r,t[u].len,t[u].sum,t[u].mx,t[u].numx);
		return ;
	}
	if(t[u].l>r||t[u].r<l) return;
	pushdown(u);
	update(ls,l,r,z);update(rs,l,r,z);
	pushup(t[u],t[ls],t[rs]);
	//printf("[%d,%d]:%d %d %d %d\n",t[u].l,t[u].r,t[u].len,t[u].sum,t[u].mx,t[u].numx);
	return;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	build(1,1,n);
	while(m--){
		op=read(),x=read(),y=read();
		if(op==2) printf("%lld\n",max(0ll,query(1,x,y).mx));
		else{z=read();update(1,x,y,z);
		//for(int i=1;i<=n;++i){
			//printf("%lld ",query(1,x,y).sum);
		}
	}
	return 0;
}