#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=1e5+10;
const ll INF=1e15;
int n,Q,p[N];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define pfl pair<Func,ll>
#define mpr make_pair
#define fi first
#define se second
struct Func{
	int k;
	ll b;
	inline friend Func operator+(const Func &a,const Func &b){
		return (Func){a.k+b.k,a.b+b.b};
	}
	inline void add(ll v){ b+=k*v; }
	inline void set(){ k=0; }
};
inline pfl max(Func a,Func b){
	if(a.k<b.k||a.k==b.k&&a.b<b.b) swap(a,b);
	if(a.b>=b.b) return mpr(a,INF);
	return mpr(b,(b.b-a.b)/(a.k-b.k));
}
struct node{
	Func lmax,rmax,totmax,sum;
	ll x;
	inline friend node operator+(const node &a,const node &b){
		node t;
		pfl tmp;
		t.x=min(a.x,b.x);
		tmp=max(a.lmax,b.lmax+a.sum);
		t.lmax=tmp.fi,t.x=min(t.x,tmp.se);
		tmp=max(b.rmax,a.rmax+b.sum);
		t.rmax=tmp.fi,t.x=min(t.x,tmp.se);
		tmp=max(a.totmax,b.totmax);
		t.x=min(t.x,tmp.se);
		tmp=max(tmp.fi,a.rmax+b.lmax);
		t.totmax=tmp.fi,t.x=min(t.x,tmp.se);
		t.sum=a.sum+b.sum;
		return t;
	}
	inline node set(){
		node a=*this;
		a.lmax.set(),a.rmax.set(),a.totmax.set(),a.sum.set();
		return a;
	}
};
struct KTT{
	node a[N<<2];
	ll tag[N<<2],mnn[N<<2],sec[N<<2];
	inline void pushup(int rt){
		if(mnn[ls]==mnn[rs]){
			mnn[rt]=mnn[ls];
			sec[rt]=min(sec[ls],sec[rs]); 
			a[rt]=a[ls]+a[rs];
		}
		if(mnn[ls]<mnn[rs]){
			mnn[rt]=mnn[ls];
			sec[rt]=min(sec[ls],mnn[rs]); 
			a[rt]=a[ls]+a[rs].set();
		}
		if(mnn[ls]>mnn[rs]){
			mnn[rt]=mnn[rs];
			sec[rt]=min(mnn[ls],sec[rs]); 
			a[rt]=a[ls].set()+a[rs];
		}
	}
	inline void build(int rt,int l,int r){
		tag[rt]=-INF;
		if(l==r){
			Func q={1,p[l]};
			a[rt]=(node){q,q,q,q,INF};
			mnn[rt]=p[l],sec[rt]=INF;
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(rt);
	}
	inline void push(int rt,ll w){
		if(w<=mnn[rt]) return ;
		ll v=w-mnn[rt];
		mnn[rt]=w;
		tag[rt]=max(tag[rt],w);
		a[rt].x-=v;
		a[rt].lmax.add(v);
		a[rt].rmax.add(v);
		a[rt].sum.add(v);
		a[rt].totmax.add(v);
	}
	inline void defeat(int rt,int l,int r,ll v){
		tag[rt]=max(tag[rt],v);
		if(v-mnn[rt]>a[rt].x){
			int mid=l+r>>1;
			defeat(ls,l,mid,v);
			defeat(rs,mid+1,r,v);
			pushup(rt);
		}else{
			push(rt,v);
		}
	}
	inline void pushdown(int rt){
		if(tag[rt]!=-INF){
			ll bas=tag[rt];
			tag[rt]=-INF;
			push(ls,bas);
			push(rs,bas);
		}
	}
	inline void update(int rt,int l,int r,int L,int R,int k){
		if(mnn[rt]>=k) return ;
		if(L<=l&&r<=R&&k<sec[rt]){
			defeat(rt,l,r,k);
			return ;
		}
		pushdown(rt);
		int mid=l+r>>1;
		if(L<=mid) update(ls,l,mid,L,R,k);
		if(R>mid) update(rs,mid+1,r,L,R,k);
		pushup(rt);
	}
	inline node query(int rt,int l,int r,int L,int R){
		if(L<=l&&r<=R){
			return a[rt];
		}
		pushdown(rt);
		int mid=l+r>>1;
		if(R<=mid) return query(ls,l,mid,L,R);
		if(L>mid) return query(rs,mid+1,r,L,R);
		return query(ls,l,mid,L,mid)+query(rs,mid+1,r,mid+1,R);
	}
}t;
int main(){
	n=read(),Q=read();
	for(int i=1;i<=n;i++){
		p[i]=read();
	}
	t.build(1,1,n);
	while(Q--){
		int opt=read();
		switch(opt){
			case 0:{
				int l=read(),r=read(),v=read();
				t.update(1,1,n,l,r,v);
				break;
			}
			case 1:{
				int l=read(),r=read();
				write(max(0ll,t.query(1,1,n,l,r).totmax.b)),putc('\n');
				break;
			}
		}
	}
	flush();
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:141:11: error: ‘read’ was not declared in this scope; did you mean ‘fread’?
  141 |         n=read(),Q=read();
      |           ^~~~
      |           fread
answer.code:151:50: error: ‘r’ was not declared in this scope
  151 |                                 t.update(1,1,n,l,r,v);
      |                                                  ^
answer.code:151:52: error: ‘v’ was not declared in this scope
  151 |                                 t.update(1,1,n,l,r,v);
      |                                                    ^
answer.code:156:63: error: ‘r’ was not declared in this scope
  156 |                                 write(max(0ll,t.query(1,1,n,l,r).totmax.b)),putc('\n');
      |                                                               ^
answer.code:156:33: error: ‘write’ was not declared in this scope; did you mean ‘fwrite’?
  156 |                                 write(max(0ll,t.query(1,1,n,l,r).totmax.b)),putc('\n');
      |                                 ^~~~~
      |                                 fwrite
answer.code:156:81: error: too few arguments to function ‘int putc(int, FILE*)’
  156 |                                 write(max(0ll,t.query(1,1,n,l,r).totmax.b)),putc('\n');
      |                                                                             ~~~~^~~~~~
In file included from /usr/include/c++/13/cstdio:42,
                 from /usr/include/c++/13/ext/string_conversions.h:45,
                 from /usr/include/c++/13/bits/basic_string.h:4097,
                 from /usr/include/c++/13/string:54,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:1:
/usr/include/stdio.h:522:12: note: declared here
  522 | extern int putc (int __c, FILE *__stream);
      |            ^~~~
answer.code:161:14: error: no matching function for call to ‘flush()’
  161 |         flush();
      |         ~~~~~^~
In file included from /usr/include/c++/13/istream:41,
                 from /usr/include/c++/13/sstream:40,
                 from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/ostream:757:5: note: candidate: ‘template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::flush(basic_ostream<_CharT, _Traits>&)’
  757 |     flush(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~~
/usr/include/c++/13/ostream:757:5: note:   template argument deduction/substitution failed:
answer.code:161:14: note:   candidate expects 1 argument, 0 provided
  161 |         flush();
      |         ~~~~~^~