#include <bits/stdc++.h>
using namespace std;
int A[100006];
struct ll {
  int l, r, sum;
  int lmx, rmx, lmi, rmi, mx, mi;
  int idl, idr, Idl, Idr;
  int mxl, mxr, mil, mir;
} tr[100006 << 2];
struct lll {
  int l, r, val, fl;
  ll num;
  bool operator<(const lll &a) const { return val < a.val; }
};
void Up(ll &a, ll b, ll c) {
  a.sum = b.sum + c.sum;
  if (b.sum + c.lmx > b.lmx)
    a.idl = c.idl;
  else
    a.idl = b.idl;
  if (c.sum + b.rmx > c.rmx)
    a.idr = b.idr;
  else
    a.idr = c.idr;
  if (b.sum + c.lmi < b.lmi)
    a.Idl = c.Idl;
  else
    a.Idl = b.Idl;
  if (c.sum + b.rmi < c.rmi)
    a.Idr = b.Idr;
  else
    a.Idr = c.Idr;
  a.lmx = max(b.sum + c.lmx, b.lmx), a.lmi = min(b.sum + c.lmi, b.lmi);
  a.rmx = max(b.rmx + c.sum, c.rmx), a.rmi = min(b.rmi + c.sum, c.rmi);
  a.mx = max(b.mx, c.mx), a.mi = min(b.mi, c.mi);
  if (b.mx > c.mx)
    a.mxl = b.mxl, a.mxr = b.mxr;
  else
    a.mxl = c.mxl, a.mxr = c.mxr;
  if (b.mi < c.mi)
    a.mil = b.mil, a.mir = b.mir;
  else
    a.mil = c.mil, a.mir = c.mir;
  if (b.rmx + c.lmx > a.mx) a.mxl = b.idr, a.mxr = c.idl;
  if (b.rmi + c.lmi < a.mi) a.mil = b.Idr, a.mir = c.Idl;
  a.mx = max(a.mx, b.rmx + c.lmx);
  a.mi = min(a.mi, b.rmi + c.lmi);
}
void build(int l, int r, int p) {
  tr[p].l = l, tr[p].r = r;
  if (l == r) {
    tr[p].sum = tr[p].mx = tr[p].lmx = tr[p].rmx = tr[p].lmi = tr[p].rmi =
        tr[p].mi = A[l];
    tr[p].idl = tr[p].idr = tr[p].Idl = tr[p].Idr = tr[p].mil = tr[p].mir =
        tr[p].mxl = tr[p].mxr = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
  Up(tr[p], tr[p << 1], tr[p << 1 | 1]);
}
void update(int x, int p) {
  if (tr[p].l == x && tr[p].r == x) {
    tr[p].sum = tr[p].mx = tr[p].lmx = tr[p].rmx = tr[p].lmi = tr[p].rmi =
        tr[p].mi = A[x];
    return;
  }
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (mid >= x)
    update(x, p << 1);
  else
    update(x, p << 1 | 1);
  Up(tr[p], tr[p << 1], tr[p << 1 | 1]);
}
ll query(int l, int r, int p) {
  if (tr[p].l == l && tr[p].r == r) return tr[p];
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (mid >= r) return query(l, r, p << 1);
  if (mid < l) return query(l, r, p << 1 | 1);
  ll a = query(l, mid, p << 1), b = query(mid + 1, r, p << 1 | 1), c;
  Up(c, a, b);
  return c;
}
priority_queue<lll> Q;
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  int m, l, r, k, opt;
  build(1, n, 1);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d", &opt);
    if (opt == 0) {
      scanf("%d%d", &l, &r);
      A[l] = r;
      update(l, 1);
    } else {
      scanf("%d%d%d", &l, &r, &k);
      while (!Q.empty()) Q.pop();
      ll now = query(l, r, 1);
      if (now.mx > 0) Q.push({l, r, now.mx, 1, now});
      int ans = 0;
      while (k--) {
        if (Q.empty()) break;
        lll t = Q.top();
        Q.pop();
        if (t.val <= 0) break;
        ans += t.val;
        ll now = t.num;
        int fl = t.fl;
        int l = fl ? now.mxl : now.mil, r = fl ? now.mxr : now.mir;
        if (t.l < l) {
          ll a = query(t.l, l - 1, 1);
          int key = fl ? a.mx : -a.mi;
          if (key > 0) Q.push({t.l, l - 1, key, fl, a});
        }
        if (r < t.r) {
          ll a = query(r + 1, t.r, 1);
          int key = fl ? a.mx : -a.mi;
          if (key > 0) Q.push({r + 1, t.r, key, fl, a});
        }
        if (l != r) {
          fl ^= 1;
          ll a = query(l, r, 1);
          int key = fl ? a.mx : -a.mi;
          if (key > 0) Q.push({l, r, key, fl, a});
        }
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}
