#include <bits/stdc++.h>
using namespace std;
int n, m, op, x, y, z, a[100010], l[100010 * 4], r[100010 * 4], la[100010 * 4];
struct xx {
  int s, l, r;
} e;
xx operator+(xx p, xx q) { return (xx){p.s + q.s, p.l, q.r}; }
bool operator<(xx p, xx q) { return p.s < q.s; }
struct ma {
  xx sum, mx, mn, lmx, lmn, rmx, rmn;
} t[100010 * 4], o, w[30];
ma operator+(ma p, ma q) {
  o.sum = p.sum + q.sum;
  o.mx = max(max(p.mx, q.mx), p.rmx + q.lmx);
  o.mn = min(min(p.mn, q.mn), p.rmn + q.lmn);
  o.lmx = max(p.lmx, p.sum + q.lmx);
  o.lmn = min(p.lmn, p.sum + q.lmn);
  o.rmx = max(q.rmx, p.rmx + q.sum);
  o.rmn = min(q.rmn, p.rmn + q.sum);
  return o;
}
void pu(int k) { t[k] = t[k * 2] + t[k * 2 + 1]; }
void W(int k, int x, int y) {
  e = (xx){x, y, y};
  t[k] = (ma){e, e, e, e, e, e, e};
}
void Q(int k) {
  la[k] ^= 1;
  t[k].sum.s *= -1;
  swap(t[k].mx, t[k].mn);
  swap(t[k].lmx, t[k].lmn);
  swap(t[k].rmx, t[k].rmn);
  t[k].mx.s *= -1;
  t[k].mn.s *= -1;
  t[k].lmx.s *= -1;
  t[k].lmn.s *= -1;
  t[k].rmx.s *= -1;
  t[k].rmn.s *= -1;
}
void pd(int k) {
  if (la[k]) {
    Q(k * 2);
    Q(k * 2 + 1);
    la[k] = 0;
  }
}
void build(int k, int z, int y) {
  l[k] = z;
  r[k] = y;
  if (z == y) {
    W(k, a[z], z);
    return;
  }
  int mid = (z + y) / 2;
  build(k * 2, z, mid);
  build(k * 2 + 1, mid + 1, y);
  pu(k);
}
void ch(int k, int u, int x) {
  if (l[k] == r[k]) {
    W(k, x, u);
    return;
  }
  pd(k);
  int mid = (l[k] + r[k]) / 2;
  if (u <= mid)
    ch(k * 2, u, x);
  else
    ch(k * 2 + 1, u, x);
  pu(k);
}
void C(int k, int z, int y) {
  if (l[k] == z && r[k] == y) {
    Q(k);
    return;
  }
  pd(k);
  int mid = (l[k] + r[k]) / 2;
  if (y <= mid)
    C(k * 2, z, y);
  else if (z > mid)
    C(k * 2 + 1, z, y);
  else
    C(k * 2, z, mid), C(k * 2 + 1, mid + 1, y);
  pu(k);
}
ma ask(int k, int z, int y) {
  if (l[k] == z && r[k] == y) return t[k];
  pd(k);
  int mid = (l[k] + r[k]) / 2;
  if (y <= mid) return ask(k * 2, z, y);
  if (z > mid) return ask(k * 2 + 1, z, y);
  return ask(k * 2, z, mid) + ask(k * 2 + 1, mid + 1, y);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, 1, n);
  cin >> m;
  while (m--) {
    scanf("%d%d%d", &op, &x, &y);
    if (!op)
      ch(1, x, y);
    else {
      scanf("%d", &z);
      int tot = 0, ans = 0;
      while (z--) {
        o = ask(1, x, y);
        if (o.mx.s <= 0) break;
        w[++tot] = o;
        ans += o.mx.s;
        C(1, o.mx.l, o.mx.r);
      }
      printf("%d\n", ans);
      while (tot) C(1, w[tot].mx.l, w[tot].mx.r), tot--;
    }
  }
}
