#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
int gi() {
  char ch = getchar();
  int x = 0, q = 0;
  while (ch < '0' || ch > '9') q = ch == '-' ? 1 : q, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return q ? -x : x;
}
struct date {
  int s, lmx, rmx, ld, rd, mx, l, r;
  void init(int w, int id) {
    s = w;
    if (w > 0)
      mx = lmx = rmx = w, l = r = ld = rd = id;
    else
      mx = lmx = rmx = 0, l = ld = id - 1, r = rd = id + 1;
    return;
  }
  void merge(const date &x, const date &y) {
    s = x.s + y.s;
    lmx = x.lmx, ld = x.ld, rmx = y.rmx, rd = y.rd;
    if (x.mx > y.mx)
      mx = x.mx, l = x.l, r = x.r;
    else
      mx = y.mx, l = y.l, r = y.r;
    if (x.rmx + y.lmx > mx) mx = x.rmx + y.lmx, l = x.rd, r = y.ld;
    if (y.lmx + x.s > lmx) lmx = y.lmx + x.s, ld = y.ld;
    if (x.rmx + y.s > rmx) rmx = x.rmx + y.s, rd = x.rd;
    return;
  }
} tr[N << 2][2], T, tmp;
int rev[N << 2], a[N], L[N], R[N], ans;
void update(int x) {
  for (int i = 0; i < 2; ++i)
    tr[x][i].merge(tr[(x << 1)][i ^ rev[(x << 1)]],
                   tr[(x << 1 | 1)][i ^ rev[(x << 1 | 1)]]);
  return;
}
void build(int x, int l, int r) {
  if (l == r) {
    tr[x][0].init(a[l], l);
    tr[x][1].init(-a[l], l);
    return;
  }
  int mid = (l + r) >> 1;
  build((x << 1), l, mid), build((x << 1 | 1), mid + 1, r);
  return update(x);
}
void insert(int x, int l, int r, int y) {
  if (l == r) {
    tr[x][0].init(a[l], l);
    tr[x][1].init(-a[l], l);
    return;
  }
  int mid = (l + r) >> 1;
  if (y <= mid)
    insert((x << 1), l, mid, y);
  else
    insert((x << 1 | 1), mid + 1, r, y);
  return update(x);
}
void modify(int x, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    rev[x] ^= 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) modify((x << 1), l, mid, ql, qr);
  if (qr > mid) modify((x << 1 | 1), mid + 1, r, ql, qr);
  return update(x);
}
void query(int x, int l, int r, int ql, int qr, int t) {
  t ^= rev[x];
  if (ql <= l && r <= qr) {
    if (l == ql)
      T = tr[x][t];
    else
      tmp.merge(T, tr[x][t]), T = tmp;
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) query((x << 1), l, mid, ql, qr, t);
  if (qr > mid) query((x << 1 | 1), mid + 1, r, ql, qr, t);
  return;
}
int main() {
  int n = gi();
  for (int i = 1; i <= n; ++i) a[i] = gi();
  build(1, 1, n);
  int q = gi(), op, l, r, k;
  for (int i = 1; i <= q; ++i) {
    op = gi(), l = gi(), r = gi();
    if (!op)
      a[l] = r, insert(1, 1, n, l);
    else {
      int tot = 0;
      k = gi(), ans = 0;
      while (tot < k) {
        query(1, 1, n, l, r, 0);
        if (T.mx <= 0) break;
        ans += T.mx, ++tot, L[tot] = T.l, R[tot] = T.r;
        modify(1, 1, n, T.l, T.r);
      }
      printf("%d\n", ans);
      while (tot) modify(1, 1, n, L[tot], R[tot]), --tot;
    }
  }
  return 0;
}
