#include <bits/stdc++.h>
using namespace std;
int a[200020], n, i, m, op, x, y, j, k, X[200020], Y[200020], xn, ret;
struct MyPair {
  int val, Left, Right;
  MyPair() {}
  MyPair(int val, int Left, int Right) : val(val), Left(Left), Right(Right) {}
  bool operator<(const MyPair& he) const { return val < he.val; }
};
inline MyPair operator+(const MyPair& a, const MyPair& b) {
  MyPair c = MyPair(a.val + b.val, min(a.Left, b.Left), max(b.Right, a.Right));
  return c;
}
struct node {
  bool push;
  int l, r, sum;
  MyPair MaxLeft, MaxRight, MaxSum;
  MyPair MinLeft, MinRight, MinSum;
  node() : push(false) {}
  node(int val, int idx) : l(idx), r(idx), sum(val) {
    MaxLeft = MaxRight = MaxSum = MinLeft = MinRight = MinSum =
        MyPair(val, idx, idx);
    push = false;
  }
} tree[200020 * 4], ct;
node c;
inline node operator+(const node& a, const node& b) {
  c.push = false;
  c.l = a.l, c.r = b.r;
  c.sum = a.sum + b.sum;
  c.MaxLeft = max(a.MaxLeft, MyPair(a.sum, a.l, a.r) + b.MaxLeft);
  c.MaxRight = max(b.MaxRight, MyPair(b.sum, b.l, b.r) + a.MaxRight);
  c.MaxSum = a.MaxRight + b.MaxLeft;
  c.MaxSum = max(c.MaxSum, a.MaxSum);
  c.MaxSum = max(c.MaxSum, b.MaxSum);
  c.MinLeft = min(a.MinLeft, MyPair(a.sum, a.l, a.r) + b.MinLeft);
  c.MinRight = min(b.MinRight, MyPair(b.sum, b.l, b.r) + a.MinRight);
  c.MinSum = a.MinRight + b.MinLeft;
  c.MinSum = min(c.MinSum, a.MinSum);
  c.MinSum = min(c.MinSum, b.MinSum);
  return c;
}
void init(int pos, int l, int r) {
  tree[pos].l = l, tree[pos].r = r;
  if (l < r) {
    init(pos + pos, l, (l + r) / 2);
    init(pos + pos + 1, (l + r) / 2 + 1, r);
    tree[pos] = tree[pos + pos] + tree[pos + pos + 1];
  } else
    tree[pos] = node(a[l], l);
}
inline void do_push(node& me) {
  me.sum *= -1;
  swap(me.MaxLeft, me.MinLeft);
  me.MaxLeft.val *= -1;
  me.MinLeft.val *= -1;
  swap(me.MaxRight, me.MinRight);
  me.MaxRight.val *= -1, me.MinRight.val *= -1;
  swap(me.MaxSum, me.MinSum);
  me.MaxSum.val *= -1, me.MinSum.val *= -1;
  me.push = false;
}
inline void refresh(int idx, int d) {
  if (tree[idx].push) {
    do_push(tree[idx]);
    if (tree[idx].l != tree[idx].r) {
      tree[idx + idx].push ^= true;
      tree[idx + idx + 1].push ^= true;
    }
  }
}
void modify(int pos, int j, int x) {
  refresh(pos, 0);
  if (tree[pos].l == tree[pos].r)
    tree[pos] = node(x, j);
  else {
    if (tree[pos + pos].r >= j)
      modify(pos + pos, j, x);
    else
      modify(pos + pos + 1, j, x);
    refresh(pos + pos, 0);
    refresh(pos + pos + 1, 0);
    tree[pos] = tree[pos + pos] + tree[pos + pos + 1];
  }
}
void change(int pos, int l, int r) {
  refresh(pos, 0);
  if (tree[pos].l == l && tree[pos].r == r) {
    tree[pos].push = true;
    refresh(pos, 0);
  } else {
    if (l <= min(r, tree[pos + pos].r))
      change(pos + pos, l, min(r, tree[pos + pos].r));
    if (max(l, tree[pos + pos + 1].l) <= r)
      change(pos + pos + 1, max(l, tree[pos + pos + 1].l), r);
    refresh(pos + pos, 0);
    refresh(pos + pos + 1, 0);
    tree[pos] = tree[pos + pos] + tree[pos + pos + 1];
  }
}
node query(int pos, int l, int r) {
  refresh(pos, 0);
  if (tree[pos].l != tree[pos].r) {
    refresh(pos + pos, 0);
    refresh(pos + pos + 1, 0);
    tree[pos] = tree[pos + pos] + tree[pos + pos + 1];
  }
  if (tree[pos].l == l && tree[pos].r == r)
    return tree[pos];
  else {
    if (tree[pos + pos].r >= r) return query(pos + pos, l, r);
    if (tree[pos + pos + 1].l <= l) return query(pos + pos + 1, l, r);
    return query(pos + pos, l, tree[pos + pos].r) +
           query(pos + pos + 1, tree[pos + pos + 1].l, r);
  }
}
int main(int argc, char* const argv[]) {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  init(1, 1, n);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 0) {
      a[x] = y;
      modify(1, x, y);
    } else {
      scanf("%d", &k);
      xn = ret = 0;
      for (j = 1; j <= k; j++) {
        ct = query(1, x, y);
        if (ct.MaxSum.val < 0) break;
        ret += ct.MaxSum.val;
        change(1, ct.MaxSum.Left, ct.MaxSum.Right);
        X[++xn] = ct.MaxSum.Left;
        Y[xn] = ct.MaxSum.Right;
      }
      for (j = 1; j <= xn; j++) change(1, X[j], Y[j]);
      printf("%d\n", ret);
    }
  }
  return 0;
}
