#include <bits/stdc++.h>
using namespace std;
struct zero {
  int sum, lmn, lmx, lmnp, lmxp, rmn, rmx, rmnp, rmxp, smx, smxl, smxr, smn,
      smnl, smnr, tag;
  zero(int p = 0, int v = 0) {
    lmxp = lmnp = rmxp = rmnp = smxl = smxr = smnl = smnr = p;
    sum = lmx = rmx = lmn = rmn = smx = smn = v;
    tag = 0;
  }
} tree[400005];
int input[400005];
zero operator+(zero a, zero b) {
  zero p;
  p.sum = a.sum + b.sum;
  (a.lmx > (a.sum + b.lmx)) ? (p.lmx = a.lmx, p.lmxp = a.lmxp)
                            : (p.lmx = a.sum + b.lmx, p.lmxp = b.lmxp);
  (b.rmx > (b.sum + a.rmx)) ? (p.rmx = b.rmx, p.rmxp = b.rmxp)
                            : (p.rmx = b.sum + a.rmx, p.rmxp = a.rmxp);
  (a.lmn < (a.sum + b.lmn)) ? (p.lmn = a.lmn, p.lmnp = a.lmnp)
                            : (p.lmn = a.sum + b.lmn, p.lmnp = b.lmnp);
  (b.rmn < (b.sum + a.rmn)) ? (p.rmn = b.rmn, p.rmnp = b.rmnp)
                            : (p.rmn = b.sum + a.rmn, p.rmnp = a.rmnp);
  (a.smx > b.smx) ? (p.smx = a.smx, p.smxl = a.smxl, p.smxr = a.smxr)
                  : (p.smx = b.smx, p.smxl = b.smxl, p.smxr = b.smxr);
  if (a.rmx + b.lmx > p.smx)
    p.smx = a.rmx + b.lmx, p.smxl = a.rmxp, p.smxr = b.lmxp;
  (a.smn < b.smn) ? (p.smn = a.smn, p.smnl = a.smnl, p.smnr = a.smnr)
                  : (p.smn = b.smn, p.smnl = b.smnl, p.smnr = b.smnr);
  if (a.rmn + b.lmn < p.smn)
    p.smn = a.rmn + b.lmn, p.smnl = a.rmnp, p.smnr = b.lmnp;
  return p;
}
void push_up(int x) { tree[x] = tree[x << 1] + tree[x << 1 | 1]; }
void build(int x, int l, int r) {
  if (l == r) {
    tree[x] = zero(l, input[l]);
    return;
  }
  build(x << 1, l, ((l + r) >> 1));
  build(x << 1 | 1, ((l + r) >> 1) + 1, r);
  push_up(x);
}
void rev(int x) {
  zero &it = tree[x];
  swap(it.lmx, it.lmn);
  swap(it.lmxp, it.lmnp);
  swap(it.rmx, it.rmn);
  swap(it.rmxp, it.rmnp);
  swap(it.smx, it.smn), swap(it.smxl, it.smnl), swap(it.smxr, it.smnr);
  it.tag ^= 1;
  it.lmx *= -1, it.lmn *= -1, it.rmx *= -1, it.rmn *= -1;
  it.smx *= -1, it.smn *= -1, it.sum *= -1;
}
void push_down(int x) {
  if (tree[x].tag) {
    rev(x << 1);
    rev(x << 1 | 1);
    tree[x].tag = 0;
  }
}
void update(int x, int l, int r, int pos, int v) {
  if (l == r) {
    tree[x] = zero(l, v);
    return;
  }
  push_down(x);
  if (pos <= ((l + r) >> 1))
    update(x << 1, l, ((l + r) >> 1), pos, v);
  else
    update(x << 1 | 1, ((l + r) >> 1) + 1, r, pos, v);
  push_up(x);
}
void rever(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return rev(x);
  push_down(x);
  if (L <= ((l + r) >> 1)) rever(x << 1, l, ((l + r) >> 1), L, R);
  if (((l + r) >> 1) < R) rever(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
  push_up(x);
}
zero query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return tree[x];
  push_down(x);
  if (R <= ((l + r) >> 1)) return query(x << 1, l, ((l + r) >> 1), L, R);
  if (((l + r) >> 1) < L) return query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
  return query(x << 1, l, ((l + r) >> 1), L, R) +
         query(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
}
int n, m, op, l, r, k, ans, cnt = 0;
int L[123], R[321];
zero t;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", input + i);
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 0)
      update(1, 1, n, l, r);
    else {
      scanf("%d", &k);
      ans = 0;
      while (k--) {
        t = query(1, 1, n, l, r);
        if (t.smx <= 0) break;
        ans += t.smx;
        cnt++;
        L[cnt] = t.smxl, R[cnt] = t.smxr;
        rever(1, 1, n, L[cnt], R[cnt]);
      }
      while (cnt) {
        rever(1, 1, n, L[cnt], R[cnt]);
        cnt--;
      }
      printf("%d\n", ans);
    }
  }
}
