#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v)
    is >> x;
  return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 100010;
const int INF = numeric_limits<int>::max();

namespace KTT$BEATS {

  struct DP {
    ll sum, pre, suf, tot;

    DP(ll sum, ll pre, ll suf, ll tot) : sum(sum), pre(pre), suf(suf), tot(tot) {}

    DP operator+(const DP &rhs) const {
      return DP(sum + rhs.sum, max(pre, sum + rhs.pre), max(suf + rhs.sum, rhs.suf),
                max({tot, rhs.tot, suf + rhs.pre}));
    }
  };

  struct Line {
    int k;
    ll b;

    Line(int k = 0, ll b = 0) : k(k), b(b) {}

    Line operator+(const Line &rhs) const { return Line(k + rhs.k, b + rhs.b); }

    void inc(int x) {
      b += k * (ll) x;
    }

    int defeat(const Line &rhs) const {
      //assert(b >= rhs.b);
      if (k >= rhs.k) return INF;
      return (rhs.b - b) / (k - rhs.k) + 1;
    }
  };

  int select(Line &mx, const Line &a, const Line &b) {
    if (a.b >= b.b)
      return (mx = a).defeat(b);
    return (mx = b).defeat(a);
  }

  int select3(Line &mx, const Line &a, const Line &b, const Line &c) {
    if (a.b >= b.b) {
      if (a.b >= c.b) mx = a;
      else mx = c;
    } else {
      if (b.b >= c.b) mx = b;
      else mx = c;
    }
    return min({mx.defeat(a), mx.defeat(b), mx.defeat(c)});
  }

  struct Node {
    int min, secmin, t, lazy;
    Line sum, pre, suf, tot;
  } P[N << 2];

  void upd(int o) {
    static Node ls, rs;
    ls = P[o << 1];
    rs = P[o << 1 | 1];
    if (ls.min < rs.min) {
      P[o].min = ls.min;
      P[o].secmin = min(ls.secmin, rs.min);
      rs.sum.k = rs.pre.k = rs.suf.k = rs.tot.k = 0;
    } else if (ls.min > rs.min) {
      P[o].min = rs.min;
      P[o].secmin = min(ls.min, rs.secmin);
      ls.sum.k = ls.pre.k = ls.suf.k = ls.tot.k = 0;
    } else {
      P[o].min = ls.min;
      P[o].secmin = min(ls.secmin, rs.secmin);
    }
    P[o].sum = ls.sum + rs.sum;
    P[o].t = min({ls.t, rs.t, select(P[o].pre, ls.pre, rs.pre + ls.sum),
                  select(P[o].suf, rs.suf, ls.suf + rs.sum),
                  select3(P[o].tot, ls.tot, rs.tot, ls.suf + rs.pre)});
  }

  void apply(int o, int x) {
    P[o].t -= x;
    P[o].min += x;
    P[o].lazy += x;
    P[o].sum.inc(x);
    P[o].pre.inc(x);
    P[o].suf.inc(x);
    P[o].tot.inc(x);
  }

  void pd(int o) {
    if (P[o].lazy) {
      for (int i = 0; i < 2; ++i)
        if (P[o].min - P[o].lazy == P[o << 1 | i].min)
          apply(o << 1 | i, P[o].lazy);
      P[o].lazy = 0;
    }
  }

  void build(int o, int l, int r, int *a) {
    if (l == r) {
      P[o].sum = Line(1, a[l]);
      if (a[l] >= 0)
        P[o].pre = P[o].suf = P[o].tot = Line(1, a[l]);
      else
        P[o].pre = P[o].suf = P[o].tot = Line(0, 0);
      P[o].min = a[l];
      P[o].secmin = INF;
      if (a[l] >= 0)
        P[o].t = INF;
      else
        P[o].t = -a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid, a);
    build(o << 1 | 1, mid + 1, r, a);
    upd(o);
  }

  DP query(int o, int l, int r, int ql, int qr) {
    if (ql == l && qr == r)
      return DP(P[o].sum.b, P[o].pre.b, P[o].suf.b, P[o].tot.b);
    pd(o);
    int mid = (l + r) >> 1;
    if (qr <= mid) return query(o << 1, l, mid, ql, qr);
    if (ql > mid) return query(o << 1 | 1, mid + 1, r, ql, qr);
    return query(o << 1, l, mid, ql, mid) + query(o << 1 | 1, mid + 1, r, mid + 1, qr);
  }

  void inc(int o, int l, int r, int x) {
    if (x < P[o].t) {
      apply(o, x);
      return;
    }
    if (l == r) {
      P[o].min += x;
      P[o].sum.inc(x);
      if (P[o].min >= 0) {
        P[o].pre = P[o].suf = P[o].tot = Line(1, P[o].min);
        P[o].t = INF;
      } else
        P[o].t -= x;
      return;
    }
    pd(o);
    int mid = (l + r) >> 1;
    if (P[o].min == P[o << 1].min)
      inc(o << 1, l, mid, x);
    if (P[o].min == P[o << 1 | 1].min)
      inc(o << 1 | 1, mid + 1, r, x);
    upd(o);
  }

  void lift(int o, int l, int r, int x) {
    if (P[o].min >= x) return;
    if (P[o].secmin > x)
      return inc(o, l, r, x - P[o].min);
    pd(o);
    int mid = (l + r) >> 1;
    lift(o << 1, l, mid, x);
    lift(o << 1 | 1, mid + 1, r, x);
    upd(o);
  }

  void lift(int o, int l, int r, int ql, int qr, int x) {
    if (ql == l && qr == r) return lift(o, l, r, x);
    pd(o);
    int mid = (l + r) >> 1;
    if (qr <= mid) lift(o << 1, l, mid, ql, qr, x);
    else if (ql > mid) lift(o << 1 | 1, mid + 1, r, ql, qr, x);
    else {
      lift(o << 1, l, mid, ql, mid, x);
      lift(o << 1 | 1, mid + 1, r, mid + 1, qr, x);
    }
    upd(o);
  }

}

int a[N];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  KTT$BEATS::build(1, 1, n, a);
  while (q--) {
    int opt, l, r, x;
    cin >> opt >> l >> r;
    if (opt == 0) {
      cin >> x;
      //cerr << "op " << l << ' ' << r << ' ' << x << '\n';
      KTT$BEATS::lift(1, 1, n, l, r, x);
    } else {
      cout << KTT$BEATS::query(1, 1, n, l, r).tot << '\n';
    }
  }

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}