#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

namespace IO {
	#ifndef ONLINE_JUDGE
	#define gh() getchar()
	#else
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	#endif

	char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 26) + 1];
	ui len = 0;

	inline int read() {
		char ch = gh();
		int res = 0, t = 1;
		while (ch < '0' || ch > '9') {
			t = (ch ^ '-') ? t : -1;
			ch = gh();
		}
		while (ch >= '0' && ch <= '9') {
			res = res * 10 + (ch ^ 48);
			ch = gh();
		}
		return t * res;
	}

	inline ui uread() {
		char ch = gh();
		ui res = 0;
		while (ch < '0' || ch > '9') {
			ch = gh();
		}
		while (ch >= '0' && ch <= '9') {
			res = res * 10 + (ch ^ 48);
			ch = gh();
		}
		return res;
	}

	inline void putc(char ch) {
		out[len++] = ch;
	}

	inline void write(ll x) {
		if (x > 9) {
			write(x / 10);
		}
		out[len++] = x % 10 + 48;
	}

	inline void flush() {
		fwrite(out, 1, len, stdout);
		len = 0;
	}
}

using IO::read;
using IO::uread;
using IO::write;
using IO::flush;
using IO::putc;

const ui N = 1 << 17;
const ui unit = 950;
const ui base = 255;

struct node {
	ui x; ll y;
	
	node() {}
	node(ui x, ll y): x(x), y(y) {}
	
	inline node operator+(const node &rhs) const {
		return node(x + rhs.x, y + rhs.y);
	}
	
	inline node operator-(const node &rhs) const {
		return node(x - rhs.x, y - rhs.y);
	}
	
	inline bool operator<(const node &rhs) const {
		return y * rhs.x < x * rhs.y;
	}
} *S, *T, *tmp, *x, *y, *S1, *T1, *S2, *T2, *S3, *T3, la, d1, d2;

struct Ans {
	ll sum, pre, suf, res;
	
	Ans() {}
	Ans(ll sum, ll pre, ll suf, ll res): sum(sum), pre(pre), suf(suf), res(res) {}
	
	inline Ans operator+(const Ans &rhs) const {
		return Ans(sum + rhs.sum, max(pre, sum + rhs.pre), max(rhs.suf, rhs.sum + suf), max(max(res, rhs.res), suf + rhs.pre));
	}
};

ui n, m, k, st[1 << 9], ed[1 << 9], op[N], l[N], r[N], cnt1[14][(1 << 13) + 16], cnt2[14][(1 << 13) + 16], cnt3[14][(1 << 13) + 16];
int a[N], b[1 << 14], d[N];
ll sum[13][(1 << 14) + 16], laz[13][(1 << 14) + 16], maxx;

struct lin {
	ull val;
	lin *Next;
	
	lin() {}
	lin(ull val, lin *Next): val(val), Next(Next) {}
} sor1[N], sor2[N], sor3[N], sor4[N], sor5[N];

lin *tot1, *tot2, *tot3, *tot4, *tot5;
lin *head1[base + 1], *head2[base + 1], *head3[base + 1], *head4[base + 1], *head5[base + 1];
lin *tail1[base + 1], *tail2[base + 1], *tail3[base + 1], *tail4[base + 1], *tail5[base + 1];

node lmax[13][(1 << 14) + 16], rmax[13][(1 << 14) + 16], tres[(1 << 14) + 16], res[13][(1 << 14) + 16];
Ans ans[N];

inline void push_up(const ui dep, const ui l, const ui r, const ll lsum, const ll rsum) {
	const ui mid = (l + r) >> 1;
	const ui l1 = cnt1[dep + 1][l], l2 = cnt1[dep + 1][mid + 1];
	const ui r1 = cnt2[dep + 1][l], r2 = cnt2[dep + 1][mid + 1];
	const ui rl1 = cnt3[dep + 1][l], rl2 = cnt3[dep + 1][mid + 1];
	const node nd1 = node(mid - l + 1, lsum), nd2 = node(r - mid, rsum);
	memcpy(&lmax[dep][l], &lmax[dep + 1][l], sizeof(node) * l1);
	memcpy(&rmax[dep][r - r2 + 1], &rmax[dep + 1][r - r2 + 1], sizeof(node) * r2);
	S = &lmax[dep + 1][mid + 1], T = &lmax[dep + 1][mid + l2];
	tmp = &lmax[dep][l], x = &lmax[dep][l + l1 - 1], y = &lmax[dep][l + l1 - 2];
	while (S <= T) {
		while (y >= tmp && (*x - *y) < (*S + nd1 - *y)) {
			--x, --y;
		}
		++x, ++y;
		*x = *S + nd1;
		++S;
	}
	cnt1[dep][l] = x - tmp + 1;
	S = &rmax[dep + 1][mid], T = &rmax[dep + 1][mid - r1 + 1];
	tmp = &rmax[dep][r], x = &rmax[dep][r - r2 + 1], y = &rmax[dep][r - r2 + 2];
	while (S >= T) {
		while (y <= tmp && (*x - *y) < (*S + nd2 - *y)) {
			++x, ++y;
		}
		--x, --y;
		*x = *S + nd2;
		--S;
	}
	cnt2[dep][l] = tmp - x + 1;
	S1 = &rmax[dep + 1][mid], S2 = &lmax[dep + 1][mid + 1];
	T1 = &rmax[dep + 1][mid - r1 + 1], T2 = &lmax[dep + 1][mid + l2];
	la = *S1 + *S2, d1 = *(S1 - 1) - *S1, d2 = *(S2 + 1) - *S2;
	tres[l + 1] = la;
	while (S1 > T1 && S2 < T2) {
		if (d2 < d1) {
			la = la + d1;
			--S1, d1 = *(S1 - 1) - *S1;
		} else {
			la = la + d2;
			++S2, d2 = *(S2 + 1) - *S2;
		}
		tres[l + la.x - 1] = la;
	}
	while (S1 > T1) {
		la = la + *(S1 - 1) - *S1, --S1;
		tres[l + la.x - 1] = la;
	}
	while (S2 < T2) {
		la = la + *(S2 + 1) - *S2, ++S2;
		tres[l + la.x - 1] = la;
	}
	S1 = &res[dep + 1][l], S2 = &res[dep + 1][mid + 1];
	res[dep][l] = node(1, max(S1 -> y, S2 -> y));
	++S1, ++S2;
	T1 = &res[dep + 1][l + rl1 - 1], T2 = &res[dep + 1][mid + rl2];
	while (S1 <= T1) {
		node &p = tres[l + (S1 -> x) - 1];
		if (!p.x) {
			p = *S1;
		} else {
			p.y = max(p.y, S1 -> y);
		}
		++S1;
	}
	while (S2 <= T2) {
		node &p = tres[l + (S2 -> x) - 1];
		if (!p.x) {
			p = *S2;
		} else {
			p.y = max(p.y, S2 -> y);
		}
		++S2;
	}
	S1 = &res[dep][l], S2 = &tres[l + 1], T2 = &tres[r];
	x = &res[dep][l], y = &res[dep][l - 1];
	while (S2 <= T2) {
		if (S2 -> x) {
			while (y >= S1 && (*x - *y) < (*S2 - *y)) {
				--x, --y;
			}
			++x, ++y;
			*x = *S2;
			*S2 = node(0, 0);
		}
		++S2;
	}
	cnt3[dep][l] = x - S1 + 1;
	sum[dep][l] = lsum + rsum;
}

inline void add(const ui dep, const ui l, const ui r, const ll t) {
	S1 = &lmax[dep][l], S2 = &rmax[dep][r], S3 = &res[dep][l];
	T1 = &lmax[dep][l + cnt1[dep][l] - 1], T2 = &rmax[dep][r - cnt2[dep][l] + 1], T3 = &res[dep][l + cnt3[dep][l] - 1];
	while (S1 <= T1) {
		S1 -> y += (S1 -> x) * t, ++S1;
	}
	while (S2 >= T2) {
		S2 -> y += (S2 -> x) * t, --S2;
	}
	while (S3 <= T3) {
		S3 -> y += (S3 -> x) * t, ++S3;
	}
	sum[dep][l] += t * (r - l + 1);
}

inline void push_down(const ui dep, const ui l, const ui r) {
	ll t = laz[dep][l];
	if (!t) {
		return;
	}
	const ui mid = (l + r) >> 1;
	laz[dep + 1][l] += t, laz[dep + 1][mid + 1] += t;
	add(dep + 1, l, mid, t), add(dep + 1, mid + 1, r, t);
	laz[dep][l] = 0;
}

inline void build(const ui dep, const ui l, const ui r) {
	laz[dep][l] = 0;
	if (l == r) {
		lmax[dep][l] = rmax[dep][l] = res[dep][l] = node(1, b[l]);
		cnt1[dep][l] = cnt2[dep][l] = cnt3[dep][l] = 1;
		sum[dep][l] = b[l];
		return;
	}
	const ui mid = (l + r) >> 1;
	build(dep + 1, l, mid), build(dep + 1, mid + 1, r);
	push_up(dep, l, r, sum[dep + 1][l], sum[dep + 1][mid + 1]);
}

inline void Sor() {
	lin *S;
	ull tmp = 0;
	for (ui j = 0; j <= base; ++j) {
		S = head1[j];
		head1[j] = tail1[j] = 0;
		while (S) {
			*(++tot2) = lin(S -> val, 0);
			tmp = ((S -> val) >> 8) & base;
			if (!head2[tmp]) {
				head2[tmp] = tail2[tmp] = tot2;
			} else {
				tail2[tmp] -> Next = tot2;
				tail2[tmp] = tot2;
			}
			S = S -> Next;
		}
	}
	for (ui j = 0; j <= base; ++j) {
		S = head2[j];
		head2[j] = tail2[j] = 0;
		while (S) {
			*(++tot3) = lin(S -> val, 0);
			tmp = ((S -> val) >> 16) & base;
			if (!head3[tmp]) {
				head3[tmp] = tail3[tmp] = tot3;
			} else {
				tail3[tmp] -> Next = tot3;
				tail3[tmp] = tot3;
			}
			S = S -> Next;
		}
	}
	for (ui j = 0; j <= base; ++j) {
		S = head3[j];
		head3[j] = tail3[j] = 0;
		while (S) {
			*(++tot4) = lin(S -> val, 0);
			tmp = ((S -> val) >> 24) & base;
			if (!head4[tmp]) {
				head4[tmp] = tail4[tmp] = tot4;
			} else {
				tail4[tmp] -> Next = tot4;
				tail4[tmp] = tot4;
			}
			S = S -> Next;
		}
	}
	for (ui j = 0; j <= base; ++j) {
		S = head4[j];
		head4[j] = tail4[j] = 0;
		while (S) {
			*(++tot5) = lin(S -> val, 0);
			tmp = ((S -> val) >> 32) & base;
			if (!head5[tmp]) {
				head5[tmp] = tail5[tmp] = tot5;
			} else {
				tail5[tmp] -> Next = tot5;
				tail5[tmp] = tot5;
			}
			S = S -> Next;
		}
	}
	tot1 = &sor1[0], tot2 = &sor2[0], tot3 = &sor3[0], tot4 = &sor4[0], tot5 = &sor5[0];
}

inline void get_ans(const ui len) {
	if (__builtin_expect(tot1 == &sor1[0], false)) {
		return;
	}
	Sor();
	ui id = 0;
	ll tmp = 0, x = 0, y = 0;
	S1 = &lmax[0][1], S2 = &rmax[0][len], S3 = &res[0][1];
	T1 = &lmax[0][cnt1[0][1]], T2 = &rmax[0][len - cnt2[0][1] + 1], T3 = &res[0][cnt3[0][1]];
	Ans now;
	lin *S;
	for (ui j = 0; j <= base; ++j) {
		S = head5[j];
		head5[j] = tail5[j] = 0;
		while (S) {
			id = (S -> val) >> 42, tmp = ((S -> val) & ((1ll << 42) - 1)) - 4e9;
			x = (S1 -> x) * tmp + (S1 -> y);
			while (S1 < T1) {
				y = ((S1 + 1) -> x) * tmp + ((S1 + 1) -> y);
				if (x > y) {
					break;
				}
				x = y, ++S1;
			}
			now.pre = x;
			x = (S2 -> x) * tmp + (S2 -> y);
			while (S2 > T2) {
				y = ((S2 - 1) -> x) * tmp + ((S2 - 1) -> y);
				if (x > y) {
					break;
				}
				x = y, --S2;
			}
			now.suf = x;
			x = (S3 -> x) * tmp + (S3 -> y);
			while (S3 < T3) {
				y = ((S3 + 1) -> x) * tmp + ((S3 + 1) -> y);
				if (x > y) {
					break;
				}
				x = y, ++S3;
			}
			now.res = x;
			now.sum = sum[0][1] + tmp * len;
			ans[id] = ans[id] + now;
			S = S -> Next;
		}
	}
}

inline void update(const ui ql, const ui qr, const ui dep, const ui l, const ui r, const int t) {
	if (ql <= l && r <= qr) {
		add(dep, l, r, t);
		laz[dep][l] += t;
		return;
	}
	push_down(dep, l, r);
	const ui mid = (l + r) >> 1;
	if (ql <= mid) {
		update(ql, qr, dep + 1, l, mid, t);
	}
	if (qr > mid) {
		update(ql, qr, dep + 1, mid + 1, r, t);
	}
	push_up(dep, l, r, sum[dep + 1][l], sum[dep + 1][mid + 1]);
}

inline void solve(const ui t) {
	const ui L = st[t], R = ed[t], len = R - L + 1;
	for (ui i = 1; i <= len; ++i) {
		b[i] = a[i + L - 1];
	}
	build(0, 1, len);
	ll tag = 0, tmp = 0;
	Ans now;
	int *S, *T;
	for (ui i = 1; i <= m; ++i) {
		if (l[i] > R || r[i] < L) {
			continue;
		}
		if (op[i] ^ 1) {
			if (l[i] <= L && r[i] >= R) {
				tmp = tag + 4e9;
				*(++tot1) = lin(tmp ^ ((ull)i << 42), 0);
				tmp &= base;
				if (!head1[tmp]) {
					head1[tmp] = tail1[tmp] = tot1;
				} else {
					tail1[tmp] -> Next = tot1;
					tail1[tmp] = tot1;
				}
			} else {
				now = Ans(0, 0, 0, 0);
				S = &a[max(l[i], L)], T = &a[min(r[i], R)];
				while (S <= T) {
					tmp = *S + tag;
					now = now + Ans(tmp, tmp, tmp, tmp);
					++S;
				}
				ans[i] = ans[i] + now;
			}
		} else {
			if (l[i] <= L && r[i] >= R) {
				tag += d[i];
			} else {
				const int D = d[i]; 
				get_ans(len);
				S = &a[max(l[i], L)], T = &a[min(r[i], R)];
				while (S <= T) {
					*S += D, ++S;
				}
				update(max(l[i], L) - L + 1, min(r[i], R) - L + 1, 0, 1, len, D);
			}
		}
	}
	get_ans(len);
}

int main() {
	n = uread(), m = uread();
	int *S = a + 1, *T = a + n;
	while (S <= T) {
		*S = read(), ++S;
	}
	if (n <= 50) {
		st[1] = 1, ed[1] = n;
		k = 1;
	} else if (n <= 100) {
		st[1] = 1, ed[1] = 50;
		st[2] = 51, ed[2] = n;
		k = 2;
	} else {
		st[1] = 1, ed[1] = 50; 
		k = 1;
		while (ed[k] < n - 50) {
			++k;
			st[k] = ed[k - 1] + 1, ed[k] = st[k] + unit;
		}
		ed[k] = n - 50;
		++k;
		st[k] = n - 49, ed[k] = n;
	}
	for (ui i = 1; i <= m; ++i) {
		op[i] = uread(), l[i] = uread(), r[i] = uread();
		if (op[i] ^ 2) {
			d[i] = read();
		}
	}
	tot1 = &sor1[0], tot2 = &sor2[0], tot3 = &sor3[0], tot4 = &sor4[0], tot5 = &sor5[0];
	for (ui i = 1; i <= k; ++i) {
		solve(i);
	}
	for (ui i = 1; i <= m; ++i) {
		if (op[i] ^ 1) {
			write(ans[i].res);
			putc('\n');
		}
	}
	flush();
	return 0;
}