#include <bits/stdc++.h>
int n, m, val[1048576 + 1];
void Swap(int &x, int &y) {
  int tmp = x;
  x = y, y = tmp;
}
struct Node {
  int sum, rev;
  int mxs, mxspl, mxspr, lmxs, lmxsp, rmxs, rmxsp;
  int mns, mnspl, mnspr, lmns, lmnsp, rmns, rmnsp;
  Node() {
    sum = 0, rev = 0;
    mxs = lmxs = rmxs = -1000000000, mns = lmns = rmns = 1000000000;
    mxspl = lmxsp = mnspl = lmnsp = 0, mxspr = rmxsp = mnspr = rmnsp = 1048576;
  }
  void K(int k = 0) { mxs = lmxs = rmxs = k = mns = lmns = rmns = sum = k; }
  void P(int p) {
    mxspl = mxspr = lmxsp = rmxsp = mnspl = mnspr = lmnsp = rmnsp = p;
  }
  void R() {
    sum = -sum, rev ^= 1;
    Swap(lmxs, lmns), Swap(lmxsp, lmnsp), lmxs = -lmxs, lmns = -lmns;
    Swap(rmxs, rmns), Swap(rmxsp, rmnsp), rmxs = -rmxs, rmns = -rmns;
    Swap(mxs, mns), Swap(mxspl, mnspl), Swap(mxspr, mnspr), mxs = -mxs,
                                                            mns = -mns;
  }
} ans[1048576 + 1];
struct SegTree {
  int tdep, tsiz;
  Node dat[(1048576 << 1) + 1];
  void Updat(Node &res, Node &lson, Node &rson) {
    res.sum = lson.sum + rson.sum;
    if (lson.lmxs > lson.sum + rson.lmxs)
      res.lmxs = lson.lmxs, res.lmxsp = lson.lmxsp;
    else
      res.lmxs = lson.sum + rson.lmxs, res.lmxsp = rson.lmxsp;
    if (lson.lmns < lson.sum + rson.lmns)
      res.lmns = lson.lmns, res.lmnsp = lson.lmnsp;
    else
      res.lmns = lson.sum + rson.lmns, res.lmnsp = rson.lmnsp;
    if (rson.rmxs > rson.sum + lson.rmxs)
      res.rmxs = rson.rmxs, res.rmxsp = rson.rmxsp;
    else
      res.rmxs = rson.sum + lson.rmxs, res.rmxsp = lson.rmxsp;
    if (rson.rmns < rson.sum + lson.rmns)
      res.rmns = rson.rmns, res.rmnsp = rson.rmnsp;
    else
      res.rmns = rson.sum + lson.rmns, res.rmnsp = lson.rmnsp;
    if (lson.mxs > rson.mxs)
      res.mxs = lson.mxs, res.mxspl = lson.mxspl, res.mxspr = lson.mxspr;
    else
      res.mxs = rson.mxs, res.mxspl = rson.mxspl, res.mxspr = rson.mxspr;
    if (lson.rmxs + rson.lmxs > res.mxs)
      res.mxs = lson.rmxs + rson.lmxs, res.mxspl = lson.rmxsp,
      res.mxspr = rson.lmxsp;
    if (lson.mns < rson.mns)
      res.mns = lson.mns, res.mnspl = lson.mnspl, res.mnspr = lson.mnspr;
    else
      res.mns = rson.mns, res.mnspl = rson.mnspl, res.mnspr = rson.mnspr;
    if (lson.rmns + rson.lmns < res.mns)
      res.mns = lson.rmns + rson.lmns, res.mnspl = lson.rmnsp,
      res.mnspr = rson.lmnsp;
  }
  void NodDwn(int nod) {
    if (dat[nod].rev) dat[nod << 1].R(), dat[nod << 1 | 1].R();
    dat[nod].rev = 0;
  }
  void TagDwn(int l, int r) {
    for (int dep = tdep; dep; dep--) {
      if (l >> dep) NodDwn(l >> dep);
      if ((l ^ r) >> dep) NodDwn(r >> dep);
    }
  }
  void Reverse(int l, int r) {
    l += tsiz - 1, r += tsiz + 1;
    TagDwn(l, r);
    for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (!(l & 1)) dat[l ^ 1].R();
      if (r & 1) dat[r ^ 1].R();
      Updat(dat[l >> 1], dat[(l >> 1) << 1], dat[(l >> 1) << 1 | 1]);
      Updat(dat[r >> 1], dat[(r >> 1) << 1], dat[(r >> 1) << 1 | 1]);
    }
    for (l >>= 1; l; l >>= 1) Updat(dat[l], dat[l << 1], dat[l << 1 | 1]);
  }
  void Build(int n) {
    for (++n, tdep = 0, tsiz = 1; tsiz <= n; tdep++, tsiz <<= 1)
      ;
    for (int i = 1; i < n; i++) dat[i | tsiz].K(val[i]), dat[i | tsiz].P(i);
    for (int i = tsiz - 1; i; i--) Updat(dat[i], dat[i << 1], dat[i << 1 | 1]);
  }
  void Modify(int p, int k) {
    p |= tsiz;
    for (int dep = tdep; dep; dep--) NodDwn(p >> dep);
    dat[p].K(k);
    for (p >>= 1; p; p >>= 1) Updat(dat[p], dat[p << 1], dat[p << 1 | 1]);
  }
  Node Query(int l, int r) {
    l += tsiz - 1, r += tsiz + 1;
    TagDwn(l, r);
    Node res, lres, ltmp, rres, rtmp;
    for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (!(l & 1)) Updat(ltmp, lres, dat[l ^ 1]), lres = ltmp;
      if (r & 1) Updat(rtmp, dat[r ^ 1], rres), rres = rtmp;
    }
    Updat(res, lres, rres);
    return res;
  }
} Segt;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
  Segt.Build(n);
  scanf("%d", &m);
  for (int i = 1, c, l, r, p, k, res; i <= m; i++) {
    scanf("%d", &c);
    if (c) {
      scanf("%d %d %d", &l, &r, &k);
      for (p = 1; p <= k; p++) {
        ans[p] = Segt.Query(l, r);
        if (ans[p].mxs <= 0) break;
        Segt.Reverse(ans[p].mxspl, ans[p].mxspr);
      }
      res = 0;
      for (p = 1; p <= k; p++) {
        if (ans[p].mxs <= 0) break;
        res += ans[p].mxs;
        Segt.Reverse(ans[p].mxspl, ans[p].mxspr);
      }
      printf("%d\n", res);
    } else {
      scanf("%d %d", &p, &k);
      Segt.Modify(p, val[p] = k);
    }
  }
  return 0;
}
