#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Range {
  int l, r, v;
  inline Range operator+(const Range &b) const {
    Range ret;
    ret.l = l;
    ret.r = b.r;
    ret.v = v + b.v;
    return ret;
  }
  inline bool operator<(const Range &b) const { return v < b.v; }
};
struct Seg {
  int sum;
  bool rev;
  Range lx, li, rx, ri, sx, si;
  inline Seg operator+(const Seg &b) const {
    Seg ret;
    Range L = (Range){lx.l, rx.r, sum}, R = (Range){b.lx.l, b.rx.r, b.sum};
    ret.sum = sum + b.sum;
    ret.lx = max(lx, L + b.lx);
    ret.rx = max(b.rx, rx + R);
    ret.sx = max(max(sx, b.sx), rx + b.lx);
    ret.li = min(li, L + b.li);
    ret.ri = min(b.ri, ri + R);
    ret.si = min(min(si, b.si), ri + b.li);
    ret.rev = 0;
    return ret;
  }
} t[4 * MAXN];
int n, m, op, x, y, kk, a[MAXN], zl[MAXN], zr[MAXN], ans;
Seg cur;
void build(int x, int l, int r) {
  if (l == r) {
    t[x].lx = t[x].rx = t[x].sx =
        max((Range){l, l - 1, 0}, (Range){l, l, a[l]});
    t[x].li = t[x].ri = t[x].si =
        min((Range){l, l - 1, 0}, (Range){l, l, a[l]});
    if (t[x].rx.v == 0) t[x].rx = (Range){l + 1, l, 0};
    if (t[x].ri.v == 0) t[x].ri = (Range){l + 1, l, 0};
    t[x].sum = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * x, l, mid);
  build(2 * x + 1, mid + 1, r);
  t[x] = t[2 * x] + t[2 * x + 1];
}
inline void rev(Range &a, Range &b) {
  swap(a, b);
  a.v = -a.v;
  b.v = -b.v;
}
inline void mark(int x) {
  t[x].rev ^= 1;
  rev(t[x].lx, t[x].li);
  rev(t[x].rx, t[x].ri);
  rev(t[x].sx, t[x].si);
  t[x].sum = -t[x].sum;
}
inline void pdown(int x) {
  mark(2 * x);
  mark(2 * x + 1);
  t[x].rev = 0;
}
void change(int x, int l, int r, int qp, int y) {
  if (l == r) {
    t[x].lx = t[x].rx = t[x].sx = max((Range){l, l - 1, 0}, (Range){l, l, y});
    t[x].li = t[x].ri = t[x].si = min((Range){l, l - 1, 0}, (Range){l, l, y});
    if (t[x].rx.v == 0) t[x].rx = (Range){l + 1, l, 0};
    if (t[x].ri.v == 0) t[x].ri = (Range){l + 1, l, 0};
    t[x].sum = y;
    return;
  }
  if (t[x].rev) pdown(x);
  int mid = (l + r) >> 1;
  if (qp <= mid)
    change(2 * x, l, mid, qp, y);
  else
    change(2 * x + 1, mid + 1, r, qp, y);
  t[x] = t[2 * x] + t[2 * x + 1];
}
void rever(int x, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    mark(x);
    return;
  }
  if (t[x].rev) pdown(x);
  int mid = (l + r) >> 1;
  if (ql <= mid) rever(2 * x, l, mid, ql, min(mid, qr));
  if (qr > mid) rever(2 * x + 1, mid + 1, r, max(mid + 1, ql), qr);
  t[x] = t[2 * x] + t[2 * x + 1];
}
Seg query(int x, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) return t[x];
  if (t[x].rev) pdown(x);
  int mid = (l + r) >> 1;
  if (qr <= mid) return query(2 * x, l, mid, ql, qr);
  if (ql > mid) return query(2 * x + 1, mid + 1, r, ql, qr);
  return query(2 * x, l, mid, ql, mid) +
         query(2 * x + 1, mid + 1, r, mid + 1, qr);
}
int main() {
  scanf("%d", &n);
  for (register int i = 1; i <= n; ++i) scanf("%d", a + i);
  build(1, 1, n);
  scanf("%d", &m);
  for (register int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 0) {
      change(1, 1, n, x, y);
    } else {
      scanf("%d", &kk);
      ans = 0;
      for (register int j = 1; j <= kk; ++j) {
        cur = query(1, 1, n, x, y);
        if (cur.sx.v == 0) break;
        ans += cur.sx.v;
        if (cur.sx.l <= cur.sx.r) {
          rever(1, 1, n, cur.sx.l, cur.sx.r);
          zl[++zl[0]] = cur.sx.l;
          zr[zl[0]] = cur.sx.r;
        }
      }
      printf("%d\n", ans);
      for (; zl[0]; zl[0]--) rever(1, 1, n, zl[zl[0]], zr[zl[0]]);
    }
  }
  return 0;
}
