#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int N = 4e5 + 5; 
const i64 INF = 2e18; 

struct Func {
    int k; i64 b; 
    Func(int k = 0, i64 b = 0) : k(k), b(b) {}
    friend Func operator+ (const Func a, const Func b) {
        return Func(a.k + b.k, a.b + b.b); 
    }
    inline void add(i64 v) { b += k * v; }
    inline void set(void) { k = 0; }
}; 
inline pair<Func, i64> 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 make_pair(a, INF); 
    return make_pair(b, (b.b - a.b) / (a.k - b.k)); 
}
struct Node {
    Func sum, lmax, rmax, ans; 
    i64 x; 
    Node(Func sum = Func(), Func lmax = Func(), Func rmax = Func(), Func ans = Func(), i64 x = 0) : sum(sum), lmax(lmax), rmax(rmax), ans(ans), x(x) {}
    friend Node operator+ (const Node &a, const Node &b) {
        Node t; t.sum = a.sum + b.sum; 
        t.x = min(a.x, b.x); 
        auto tmp = max(a.lmax, a.sum + b.lmax); 
        t.lmax = tmp.first, t.x = min(t.x, tmp.second); 
        tmp = max(b.rmax, b.sum + a.rmax); 
        t.rmax = tmp.first, t.x = min(t.x, tmp.second); 
        tmp = max(a.ans, b.ans); 
        t.ans = tmp.first, t.x = min(t.x, tmp.second); 
        tmp = max(tmp.first, a.rmax + b.lmax); 
        t.ans = tmp.first, t.x = min(t.x, tmp.second); 
        return t; 
    }
    inline Node set(void) {
        Node a = *this; 
        a.sum.set(); a.lmax.set(); a.rmax.set(); a.ans.set(); 
        return a; 
    }
} T[N * 4]; 

int n, q; 
int a[N]; 
i64 tag[N * 4], mn[N * 4], se[N * 4]; 

inline void pushup(int o) {
    if (mn[o << 1] == mn[o << 1 | 1]) {
        mn[o] = mn[o << 1], se[o] = min(se[o << 1], se[o << 1 | 1]); 
        T[o] = T[o << 1] + T[o << 1 | 1]; 
    } else if (mn[o << 1] < mn[o << 1 | 1]) {
        mn[o] = mn[o << 1], se[o] = min(se[o << 1], mn[o << 1 | 1]); 
        T[o] = T[o << 1] + T[o << 1 | 1].set(); 
    } else {
        mn[o] = mn[o << 1 | 1], se[o] = min(mn[o << 1], se[o << 1 | 1]); 
        T[o] = T[o << 1].set() + T[o << 1 | 1]; 
    }
}
void build(int o, int l, int r) {
    tag[o] = -INF; 
    if (l == r) {
        auto it = Func(1, a[l]); 
        T[o] = Node(it, it, it, it, INF); 
        mn[o] = a[l]; se[o] = INF; 
        return;
    }
    int mid = l + r >> 1; 
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 
    pushup(o); 
}
inline void maketag(int o, i64 k) {
    if (mn[o] >= k) return; 
    i64 v = k - mn[o]; mn[o] = k; tag[o] = k; T[o].x -= v; 
    T[o].sum.add(v); T[o].lmax.add(v); T[o].rmax.add(v); T[o].ans.add(v); 
}
inline void pushdown(int o) {
    if (tag[o] == -INF) return; 
    maketag(o << 1, tag[o]); maketag(o << 1 | 1, tag[o]); 
    tag[o] = -INF; 
}
void rebuild(int o, int l, int r, i64 k) {
    tag[o] = max(tag[o], k); 
    if (k - mn[o] > T[o].x) {
        int mid = l + r >> 1; 
        rebuild(o << 1, l, mid, tag[o]); 
        rebuild(o << 1 | 1, mid + 1, r, tag[o]); 
        pushup(o); 
        return; 
    }
    maketag(o, k); 
}
void update(int o, int l, int r, int x, int y, i64 k) {
    if (mn[o] >= k) return; 
    if (x <= l && r <= y && k < se[o]) return rebuild(o, l, r, k), void(); 
    pushdown(o); int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y, k); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k); 
    T[o] = T[o << 1] + T[o << 1 | 1]; 
}
Node query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o]; 
    pushdown(o); int mid = l + r >> 1; 
    if (y <= mid) return query(o << 1, l, mid, x, y); 
    if (mid < x) return query(o << 1 | 1, mid + 1, r, x, y); 
    return query(o << 1, l, mid, x, y) + query(o << 1 | 1, mid + 1, r, x, y); 
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> q; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    build(1, 1, n); 
    while (q--) {
        int op, l, r, v; cin >> op >> l >> r; 
        if (op == 0) cin >> v, update(1, 1, n, l, r, v); 
        else cout << max(0ll, query(1, 1, n, l, r).ans.b) << "\n"; 
    }
    return 0;
}