#pragma pack(1)
#include<cstdio>
#include<algorithm>
#include<vector> 
#include<bitset>
using namespace std;
int n,m,x,l,r,a[300009];
long long t,ans[600009];
bitset<600009>vis;
struct point{
	int x;
	long long y;
	point(int _x = 0,long long _y = 0){
		x = _x,y = _y;
	}
};
bool chk(point a,point b,point c){
	return (b.y - a.y) * (c.x - b.x) <= (c.y - b.y) * (b.x - a.x);
}
vector<point>q[1200009],h[1200009],f[1200009];
int stq[120009],sth[120009],stf[120009];
long long sum[1200009];
struct query{
	long long t;
	int id,l,r;
	bool operator<(const query &b)const{
		return t < b.t;
	}
}qu[600009];
int qcnt;
void add(const point &x,vector<point>&t){
	if(t.size() > 0){
		point u = t[t.size() - 1];
		if(u.x == x.x){
			if(u.y > x.y)
				return;
			else
				t.pop_back();
		}
	}
	while(t.size() > 1 && chk(t[t.size() - 2],t[t.size() - 1],x))
		t.pop_back();
	t.push_back(x);
}
vector<point>sq1,sq2;
void build(int k,int l,int r){
	if(l == r){
		q[k].push_back(point(1,a[l]));
		h[k].push_back(point(1,a[l]));
		f[k].push_back(point(1,a[l]));
		sum[k] = a[l];
	}
	else{
		int m = (l + r) >> 1;
		build(k << 1,l,m);
		build((k << 1) | 1,m + 1,r);
		sum[k] = sum[k << 1] + sum[(k << 1) | 1];
		q[k] = vector<point>(q[k << 1]);
		for(int i = 0; i < q[(k << 1) | 1].size(); i ++){
			point u = q[(k << 1) | 1][i];
			u.y += sum[k << 1];
			u.x += (m - l + 1);
			add(u,q[k]);
		}
		q[k].shrink_to_fit();
		h[k] = vector<point>(h[k << 1]);
		for(int i = 0; i < h[(k << 1)].size(); i ++){
			point u = h[(k << 1)][i];
			u.y += sum[(k << 1) | 1];
			u.x += (r - m);
			add(u,h[k]);
		}
		h[k].shrink_to_fit();
		int p1 = 0,p2 = 0;
		sq1 = sq2 = vector<point>(0);
		while(p1 < f[(k << 1)].size() || p2 < f[(k << 1) | 1].size()){
			if(p2 == f[(k << 1) | 1].size() || (p1 < f[(k << 1)].size() && f[k << 1][p1].x < f[(k << 1) | 1][p2].x)){
				point u = f[k << 1][p1];
				p1 ++;
				add(u,sq1);
			}
			else{
				point u = f[(k << 1) | 1][p2];
				p2 ++;
				add(u,sq1);
			}
		}
		sq1.shrink_to_fit(); 
		p1 = 0,p2 = 0;
		while(true){
			point u = point(h[k << 1][p1].x + q[(k << 1) | 1][p2].x,h[k << 1][p1].y + q[(k << 1) | 1][p2].y);
			add(u,sq2); 
			//printf("%d %d\n",p1,p2);
			if(p1 == h[k << 1].size() - 1 && p2 == q[(k << 1) | 1].size() - 1)
				break;
			if(p2 == q[(k << 1) | 1].size() - 1 || (p1 < h[k << 1].size() - 1
			 && ((h[k << 1][p1 + 1].y - h[k << 1][p1].y) * (q[1 | (k << 1)][p2 + 1].x - q[1 | (k << 1)][p2].x) > (q[1 | (k << 1)][p2 + 1].x - q[1 | (k << 1)][p2].x) * (h[k << 1][p1 + 1].x - h[k << 1][p1].x)
			  || ((h[k << 1][p1 + 1].y - h[k << 1][p1].y) * (q[1 | (k << 1)][p2 + 1].x - q[1 | (k << 1)][p2].x) == (q[1 | (k << 1)][p2 + 1].x - q[1 | (k << 1)][p2].x) * (h[k << 1][p1 + 1].x - h[k << 1][p1].x)
			  && (h[k << 1][p1 + 1].x - h[k << 1][p1].x) < (q[1 | (k << 1)][p2 + 1].x - q[1 | (k << 1)][p2].x)))))
			  	p1 ++;
			else
				p2 ++;
		}
		sq2.shrink_to_fit();
		p1 = 0,p2 = 0;
		while(p1 < sq1.size() || p2 < sq2.size()){
			if(p2 == sq2.size() || (p1 < sq1.size() && sq1[p1].x < sq2[p2].x)){
				point u = sq1[p1];
				p1 ++;
				add(u,f[k]);
			}
			else{
				point u = sq2[p2];
				p2 ++;
				add(u,f[k]);
			}
		//	printf("%d %d\n",p1,p2);
		}
		f[k].shrink_to_fit();
		//printf("%d %d\n",l,r);
		//for(int i = 0; i < q[k].size(); i ++)
		//	printf(" %d %d\n",q[k][i].x,q[k][i].y);
	//	for(int i = 0; i < h[k].size(); i ++)
	//		printf("  %d %d\n",h[k][i].x,h[k][i].y);
	//	for(int i = 0; i < f[k].size(); i ++)
	//		printf("   %d %d\n",f[k][i].x,f[k][i].y);
	}
}
long long qf = 0,qh = -998244353999911659ll;
void query(int k,int l,int r,int lq,int rq,long long t){
	while(stq[k] < q[k].size() - 1){
		long long s1 = t * q[k][stq[k]].x + q[k][stq[k]].y;
		long long s2 = t * q[k][stq[k] + 1].x + q[k][stq[k] + 1].y;
		if(s1 <= s2)
			stq[k] ++;
		else
			break;
	}
	while(sth[k] < h[k].size() - 1){
		long long s1 = t * h[k][sth[k]].x + h[k][sth[k]].y;
		long long s2 = t * h[k][sth[k] + 1].x + h[k][sth[k] + 1].y;
		if(s1 <= s2)
			sth[k] ++;
		else
			break;
	}
	while(stf[k] < f[k].size() - 1){
		long long s1 = t * f[k][stf[k]].x + f[k][stf[k]].y;
		long long s2 = t * f[k][stf[k] + 1].x + f[k][stf[k] + 1].y;
		if(s1 <= s2)
			stf[k] ++;
		else
			break;
	}
	if(l > rq || r < lq)
		return;
	if(l >= lq && r <= rq){
		long long s1 = t * f[k][stf[k]].x + f[k][stf[k]].y;
		long long s2 = t * h[k][sth[k]].x + h[k][sth[k]].y;
		long long s3 = t * q[k][stq[k]].x + q[k][stq[k]].y;
	//	printf("%d %d %d\n",s1,s2,s3);
		qf = max(qf,max(s1,s3 + qh));
		qh = max(qh + sum[k] + t * (r - l + 1),s2);
		return;
	}
	int m = (l + r) >> 1;
	query(k << 1,l,m,lq,rq,t);
	query((k << 1) | 1,m + 1,r,lq,rq,t);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(int i = 1; i <= m; i ++){
		int op;
		scanf("%d",&op);
		if(op == 1){
			scanf("%d",&x);
			t += x;
		}
		else{
			scanf("%d %d",&l,&r);
			qcnt ++;
			qu[qcnt].id = i;
			qu[qcnt].t = t;
			qu[qcnt].l = l;
			qu[qcnt].r = r;
			vis[i] = true;
		}
	}
	sort(qu + 1,qu + qcnt + 1);
	for(int i = 1; i <= qcnt; i ++){
		qf = 0,qh = -998244353999911659ll;
		query(1,1,n,qu[i].l,qu[i].r,qu[i].t);
		ans[qu[i].id] = qf;
	}
	for(int i = 1; i <= m; i ++)
		if(vis[i])
			printf("%lld\n",ans[i]);
}