#include <bits/stdc++.h>
using namespace std;
struct node {
  int l, r, sum, tag;
  int premx, prefr, premn, pmnfr;
  int sufmx, suffr, sufmn, smnfr;
  int mx, mxfrl, mxfrr, mn, mnfrl, mnfrr;
  node *lch, *rch;
  node operator+(node b) {
    node Ans;
    Ans.sum = sum + b.sum, Ans.l = l, Ans.r = b.r;
    Ans.tag = false, Ans.lch = Ans.rch = nullptr;
    Ans.premx = max(premx, sum + b.premx);
    if (Ans.premx == premx)
      Ans.prefr = prefr;
    else
      Ans.prefr = b.prefr;
    Ans.sufmx = max(b.sufmx, sufmx + b.sum);
    if (Ans.sufmx == b.sufmx)
      Ans.suffr = b.suffr;
    else
      Ans.suffr = suffr;
    Ans.mx = max(max(Ans.sufmx, Ans.premx), sufmx + b.premx);
    Ans.mx = max(Ans.mx, max(mx, b.mx));
    if (Ans.mx == mx)
      Ans.mxfrl = mxfrl, Ans.mxfrr = mxfrr;
    else if (Ans.mx == b.mx)
      Ans.mxfrl = b.mxfrl, Ans.mxfrr = b.mxfrr;
    else if (Ans.mx == Ans.sufmx)
      Ans.mxfrl = Ans.suffr, Ans.mxfrr = Ans.r;
    else if (Ans.mx == Ans.premx)
      Ans.mxfrl = l, Ans.mxfrr = Ans.prefr;
    else
      Ans.mxfrl = suffr, Ans.mxfrr = b.prefr;
    Ans.premn = min(premn, sum + b.premn);
    if (Ans.premn == premn)
      Ans.pmnfr = pmnfr;
    else
      Ans.pmnfr = b.pmnfr;
    Ans.sufmn = min(b.sufmn, sufmn + b.sum);
    if (Ans.sufmn == b.sufmn)
      Ans.smnfr = b.smnfr;
    else
      Ans.smnfr = smnfr;
    Ans.mn = min(min(Ans.sufmn, Ans.premn), sufmn + b.premn);
    Ans.mn = min(Ans.mn, min(mn, b.mn));
    if (Ans.mn == mn)
      Ans.mnfrl = mnfrl, Ans.mnfrr = mnfrr;
    else if (Ans.mn == b.mn)
      Ans.mnfrl = b.mnfrl, Ans.mnfrr = b.mnfrr;
    else if (Ans.mn == Ans.sufmn)
      Ans.mnfrl = Ans.smnfr, Ans.mnfrr = Ans.r;
    else if (Ans.mn == Ans.premn)
      Ans.mnfrl = l, Ans.mnfrr = Ans.pmnfr;
    else
      Ans.mnfrl = smnfr, Ans.mnfrr = b.pmnfr;
    return Ans;
  }
} * root, POOL[(100000 + 54) * 2];
int cnt, a[(100000 + 54)];
void dooppo(node *x) {
  x->tag ^= 1, x->sum *= -1;
  swap(x->prefr, x->pmnfr), swap(x->premx, x->premn);
  x->premx *= -1, x->premn *= -1;
  swap(x->suffr, x->smnfr), swap(x->sufmx, x->sufmn);
  x->sufmx *= -1, x->sufmn *= -1;
  swap(x->mxfrl, x->mnfrl), swap(x->mxfrr, x->mnfrr), swap(x->mx, x->mn);
  x->mx *= -1, x->mn *= -1;
}
void pushdown(node *x) {
  if (x->lch == nullptr || !x->tag) return;
  dooppo(x->lch), dooppo(x->rch);
  x->tag = false;
}
void pushup(node *x) {
  if (x->l == x->r) {
    x->premx = x->sufmx = x->mx = x->mn = x->sum;
    x->premn = x->sufmn = x->sum;
    x->pmnfr = x->smnfr = x->mnfrl = x->mnfrr = x->l;
    x->prefr = x->suffr = x->mxfrl = x->mxfrr = x->l;
  } else {
    node *l = x->lch, *r = x->rch;
    int tag = x->tag;
    *x = *x->lch + *x->rch;
    x->lch = l, x->rch = r;
    x->tag = tag;
  }
}
node *build(int l, int r) {
  node *x = &POOL[cnt++];
  x->l = l, x->r = r, x->tag = 0;
  if (l == r)
    x->sum = a[l], x->lch = x->rch = nullptr;
  else {
    int mid = (l + r) >> 1;
    x->lch = build(l, mid);
    x->rch = build(mid + 1, r);
  }
  pushup(x);
  return x;
}
void change(node *x, int p, int v) {
  if (x->lch == nullptr) return x->sum = v, pushup(x);
  int mid = (x->l + x->r) >> 1;
  pushdown(x);
  if (p <= mid)
    change(x->lch, p, v);
  else
    change(x->rch, p, v);
  return pushup(x);
}
node getmx(node *x, int l, int r) {
  if (l <= x->l && x->r <= r) return *x;
  int mid = (x->l + x->r) >> 1;
  pushdown(x);
  if (l <= mid && mid < r) return getmx(x->lch, l, r) + getmx(x->rch, l, r);
  if (l <= mid) return getmx(x->lch, l, r);
  return getmx(x->rch, l, r);
}
void oppo(node *x, int l, int r) {
  if (l <= x->l && x->r <= r) return dooppo(x);
  int mid = (x->l + x->r) >> 1;
  pushdown(x);
  if (l <= mid) oppo(x->lch, l, r);
  if (r > mid) oppo(x->rch, l, r);
  return pushup(x);
}
void out(node *x) {
  pushdown(x);
  if (x->lch == nullptr) {
    cout << x->sum << " ";
    return;
  }
  out(x->lch), out(x->rch);
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  root = build(1, n);
  int m;
  cin >> m;
  for (int i = 1, op, l, r, v; i <= m; ++i) {
    cin >> op;
    if (op == 0) {
      cin >> l >> v;
      change(root, l, v);
    } else {
      cin >> l >> r >> v;
      int Ans = 0;
      int L[22] = {0}, R[22] = {0};
      for (int j = 1; j <= v + 1; ++j) {
        node tmp = getmx(root, l, r);
        if (j == v + 1 || tmp.mx <= 0) {
          cout << Ans << endl;
          while (--j) {
            oppo(root, L[j], R[j]);
          }
          break;
        }
        Ans += tmp.mx;
        L[j] = tmp.mxfrl, R[j] = tmp.mxfrr;
        oppo(root, L[j], R[j]);
      }
    }
  }
  return 0;
}
