#include <bits/stdc++.h>
using namespace std;
int rd() {
  int x = 0, flg = 1;
  char c = getchar();
  for (; (c < 48 || c > 57) && c != '-'; c = getchar())
    ;
  if (c == '-') flg = -1, c = getchar();
  for (; c > 47 && c < 58; x = x * 10 + c - 48, c = getchar())
    ;
  return flg * x;
}
const int mxn = 100010;
struct nd {
  int sm, px, py, sx, sy, mx, ml, mr, _px, _py, _sx, _sy, _mx, _ml, _mr;
  nd operator!() {
    return (nd){-sm, -_px, _py, -_sx, _sy, -_mx, _ml, _mr,
                -px, py,   -sx, sy,   -mx, ml,   mr};
  }
} tr[mxn << 2], ret;
int tag[mxn << 2];
void mrg(nd x, nd y) {
  ret.sm = x.sm + y.sm;
  if (x.px < x.sm + y.px)
    ret.px = x.px, ret.py = x.py;
  else
    ret.px = x.sm + y.px, ret.py = y.py;
  if (y.sx < y.sm + x.sx)
    ret.sx = y.sx, ret.sy = y.sy;
  else
    ret.sx = y.sm + x.sx, ret.sy = x.sy;
  if (x.mx < y.mx)
    if (x.mx < x.sx + y.px)
      ret.mx = x.mx, ret.ml = x.ml, ret.mr = x.mr;
    else
      ret.mx = x.sx + y.px, ret.ml = x.sy, ret.mr = y.py;
  else if (y.mx < x.sx + y.px)
    ret.mx = y.mx, ret.ml = y.ml, ret.mr = y.mr;
  else
    ret.mx = x.sx + y.px, ret.ml = x.sy, ret.mr = y.py;
  if (x._px > x.sm + y._px)
    ret._px = x._px, ret._py = x._py;
  else
    ret._px = x.sm + y._px, ret._py = y._py;
  if (y._sx > y.sm + x._sx)
    ret._sx = y._sx, ret._sy = y._sy;
  else
    ret._sx = y.sm + x._sx, ret._sy = x._sy;
  if (x._mx > y._mx)
    if (x._mx > x._sx + y._px)
      ret._mx = x._mx, ret._ml = x._ml, ret._mr = x._mr;
    else
      ret._mx = x._sx + y._px, ret._ml = x._sy, ret._mr = y._py;
  else if (y._mx > x._sx + y._px)
    ret._mx = y._mx, ret._ml = y._ml, ret._mr = y._mr;
  else
    ret._mx = x._sx + y._px, ret._ml = x._sy, ret._mr = y._py;
}
void mrg_rev(nd x, nd y) {
  ret.sm = -x.sm - y.sm;
  if (x._px > x.sm + y._px)
    ret.px = -x._px, ret.py = x._py;
  else
    ret.px = -x.sm - y._px, ret.py = y._py;
  if (y._sx > y.sm + x._sx)
    ret.sx = -y._sx, ret.sy = y._sy;
  else
    ret.sx = -y.sm - x._sx, ret.sy = x._sy;
  if (x._mx > y._mx)
    if (x._mx > x._sx + y._px)
      ret.mx = -x._mx, ret.ml = x._ml, ret.mr = x._mr;
    else
      ret.mx = -x._sx - y._px, ret.ml = x._sy, ret.mr = y._py;
  else if (y._mx > x._sx + y._px)
    ret.mx = -y._mx, ret.ml = y._ml, ret.mr = y._mr;
  else
    ret.mx = -x._sx - y._px, ret.ml = x._sy, ret.mr = y._py;
  if (x.px < x.sm + y.px)
    ret._px = -x.px, ret._py = x.py;
  else
    ret._px = -x.sm - y.px, ret._py = y.py;
  if (y.sx < y.sm + x.sx)
    ret._sx = -y.sx, ret._sy = y.sy;
  else
    ret._sx = -y.sm - x.sx, ret._sy = x.sy;
  if (x.mx < y.mx)
    if (x.mx < x.sx + y.px)
      ret._mx = -x.mx, ret._ml = x.ml, ret._mr = x.mr;
    else
      ret._mx = -x.sx - y.px, ret._ml = x.sy, ret._mr = y.py;
  else if (y.mx < x.sx + y.px)
    ret._mx = -y.mx, ret._ml = y.ml, ret._mr = y.mr;
  else
    ret._mx = -x.sx - y.px, ret._ml = x.sy, ret._mr = y.py;
}
void pushup(int i) {
  if (tag[i])
    mrg_rev(tr[(i << 1)], tr[(i << 1 | 1)]);
  else
    mrg(tr[(i << 1)], tr[(i << 1 | 1)]);
  tr[i] = ret;
}
void update(int i, int l, int r, int p, int v) {
  if (l == r) {
    tr[i] = (nd){v, v, l, v, l, v, l, l, v, l, v, l, v, l, l};
    return;
  }
  if (p <= ((l + r) >> 1))
    update((i << 1), l, ((l + r) >> 1), p, v);
  else
    update((i << 1 | 1), ((l + r) >> 1) + 1, r, p, v);
  pushup(i);
}
void modify(int i, int l, int r, int x, int y) {
  if (r < x || l > y) return;
  if (l >= x && r <= y) {
    tag[i] ^= 1, tr[i] = !tr[i];
    return;
  }
  modify((i << 1), l, ((l + r) >> 1), x, y);
  modify((i << 1 | 1), ((l + r) >> 1) + 1, r, x, y);
  pushup(i);
}
int tot, id[mxn], fl[mxn], bl[mxn], br[mxn];
void query(int i, int l, int r, int x, int y, bool fg) {
  if (r < x || l > y) return;
  if (l >= x && r <= y) {
    id[++tot] = i;
    fl[tot] = fg;
    bl[tot] = l, br[tot] = r;
    return;
  }
  query((i << 1), l, ((l + r) >> 1), x, y, fg ^ tag[i]);
  query((i << 1 | 1), ((l + r) >> 1) + 1, r, x, y, fg ^ tag[i]);
}
void qry() {
  if (fl[1])
    ret = !tr[id[1]];
  else
    ret = tr[id[1]];
  for (int i = 2; i <= tot; ++i)
    if (fl[i])
      mrg(ret, !tr[id[i]]);
    else
      mrg(ret, tr[id[i]]);
}
int n, q, a[mxn], qi[mxn], ql[mxn], qr[mxn], qx[mxn], qy[mxn];
void build(int i, int l, int r) {
  if (l == r) {
    tr[i] =
        (nd){a[l], a[l], l, a[l], l, a[l], l, l, a[l], l, a[l], l, a[l], l, l};
    return;
  }
  build((i << 1), l, ((l + r) >> 1)),
      build((i << 1 | 1), ((l + r) >> 1) + 1, r);
  pushup(i);
}
int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  build(1, 1, n);
  q = rd();
  for (int i = 1; i <= q; ++i)
    if (rd()) {
      int l = rd(), r = rd(), k = rd(), m = 0, ans = 0;
      tot = 0;
      query(1, 1, n, l, r, 0);
      for (; k--;) {
        qry();
        if (ret._mx <= 0) break;
        ans += ret._mx;
        int x = ret._ml, y = ret._mr;
        modify(1, 1, n, x, y);
        ql[++m] = x, qr[m] = y;
      }
      printf("%d\n", ans);
      for (int j = 1; j <= m; ++j) modify(1, 1, n, ql[j], qr[j]);
    } else {
      int x = rd(), y = rd();
      update(1, 1, n, x, y);
    }
  return 0;
}
