#include <bits/stdc++.h>
using namespace std;
int n, m, val[100020];
struct Sum {
  int val, l, r;
  void rev() { val = -val; }
  void init() { val = l = r = 0; }
};
struct Node {
  int rev;
  Sum sum, maxsum, minsum, maxlsum, minlsum, maxrsum, minrsum;
  void init() {
    rev = 0;
    sum.init();
    maxsum.init();
    minsum.init();
    maxlsum.init();
    minlsum.init();
    maxrsum.init();
    minrsum.init();
  }
};
struct Tree {
  Node node[100020 * 4];
  void pushdown(int p) {
    int left = node[p].sum.l, right = node[p].sum.r;
    if (node[p].rev) {
      Node &x = node[p];
      x.sum.rev();
      x.maxsum.rev();
      x.minsum.rev();
      x.maxlsum.rev();
      x.minlsum.rev();
      x.maxrsum.rev();
      x.minrsum.rev();
      swap(x.maxsum, x.minsum);
      swap(x.maxlsum, x.minlsum);
      swap(x.maxrsum, x.minrsum);
      if (left != right) {
        node[p << 1 | 0].rev ^= 1;
        node[p << 1 | 1].rev ^= 1;
      }
      x.rev = 0;
    }
  }
  void merge(Node &x, const Node &lhs, const Node &rhs) {
    x.init();
    x.sum.val = lhs.sum.val + rhs.sum.val;
    x.sum.l = lhs.sum.l;
    x.sum.r = rhs.sum.r;
    if (lhs.maxsum.val > x.maxsum.val) x.maxsum = lhs.maxsum;
    if (rhs.maxsum.val > x.maxsum.val) x.maxsum = rhs.maxsum;
    if (lhs.maxrsum.val + rhs.maxlsum.val > x.maxsum.val)
      x.maxsum.val = lhs.maxrsum.val + rhs.maxlsum.val,
      x.maxsum.l = lhs.maxrsum.l, x.maxsum.r = rhs.maxlsum.r;
    if (lhs.maxlsum.val > x.maxlsum.val) x.maxlsum = lhs.maxlsum;
    if (lhs.sum.val + rhs.maxlsum.val > x.maxlsum.val)
      x.maxlsum.val = lhs.sum.val + rhs.maxlsum.val, x.maxlsum.l = lhs.sum.l,
      x.maxlsum.r = rhs.maxlsum.r;
    if (rhs.maxrsum.val > x.maxrsum.val) x.maxrsum = rhs.maxrsum;
    if (rhs.sum.val + lhs.maxrsum.val > x.maxrsum.val)
      x.maxrsum.val = rhs.sum.val + lhs.maxrsum.val, x.maxrsum.r = rhs.sum.r,
      x.maxrsum.l = lhs.maxrsum.l;
    if (lhs.minsum.val < x.minsum.val) x.minsum = lhs.minsum;
    if (rhs.minsum.val < x.minsum.val) x.minsum = rhs.minsum;
    if (lhs.minrsum.val + rhs.minlsum.val < x.minsum.val)
      x.minsum.val = lhs.minrsum.val + rhs.minlsum.val,
      x.minsum.l = lhs.minrsum.l, x.minsum.r = rhs.minlsum.r;
    if (lhs.minlsum.val < x.minlsum.val) x.minlsum = lhs.minlsum;
    if (lhs.sum.val + rhs.minlsum.val < x.minlsum.val)
      x.minlsum.val = lhs.sum.val + rhs.minlsum.val, x.minlsum.l = lhs.sum.l,
      x.minlsum.r = rhs.minlsum.r;
    if (rhs.minrsum.val < x.minrsum.val) x.minrsum = rhs.minrsum;
    if (rhs.sum.val + lhs.minrsum.val < x.minrsum.val)
      x.minrsum.val = rhs.sum.val + lhs.minrsum.val, x.minrsum.r = rhs.sum.r,
      x.minrsum.l = lhs.minrsum.l;
  }
  void pushup(int p) {
    int left = node[p].sum.l, right = node[p].sum.r;
    int mid = (left + right) / 2;
    pushdown(p << 1 | 0);
    pushdown(p << 1 | 1);
    merge(node[p], node[p << 1 | 0], node[p << 1 | 1]);
  }
  void update(Node &x, int y, int loc) {
    x.init();
    x.sum.val = y;
    x.sum.l = x.sum.r = loc;
    if (y > x.maxsum.val) x.maxsum.val = y, x.maxsum.l = x.maxsum.r = loc;
    if (y > x.maxlsum.val) x.maxlsum.val = y, x.maxlsum.l = x.maxlsum.r = loc;
    if (y > x.maxrsum.val) x.maxrsum.val = y, x.maxrsum.l = x.maxrsum.r = loc;
    if (y < x.minsum.val) x.minsum.val = y, x.minsum.l = x.minsum.r = loc;
    if (y < x.minlsum.val) x.minlsum.val = y, x.minlsum.l = x.minlsum.r = loc;
    if (y < x.minrsum.val) x.minrsum.val = y, x.minrsum.l = x.minrsum.r = loc;
  }
  void clean(int p, int left, int right) {
    node[p].init();
    node[p].sum.l = left, node[p].sum.r = right;
    if (left == right) {
      update(node[p], val[left], left);
      return;
    }
    int mid = (left + right) / 2;
    clean(p << 1 | 0, left, mid);
    clean(p << 1 | 1, mid + 1, right);
    pushup(p);
  }
  void init() { clean(1, 1, n); }
  void modify(int p, int x, int y) {
    pushdown(p);
    int left = node[p].sum.l, right = node[p].sum.r;
    if (left == right) {
      update(node[p], y, left);
      return;
    }
    int mid = (left + right) / 2;
    if (x <= mid)
      modify(p << 1 | 0, x, y);
    else
      modify(p << 1 | 1, x, y);
    pushup(p);
  }
  void reverse(int p, int x, int y) {
    pushdown(p);
    int left = node[p].sum.l, right = node[p].sum.r;
    if (x <= left && right <= y) {
      node[p].rev ^= 1;
      return;
    }
    int mid = (left + right) / 2;
    if (x <= mid) reverse(p << 1 | 0, x, y);
    if (y > mid) reverse(p << 1 | 1, x, y);
    pushup(p);
  }
  Node query(int p, int x, int y) {
    pushdown(p);
    int left = node[p].sum.l, right = node[p].sum.r;
    if (x <= left && right <= y) return node[p];
    int mid = (left + right) / 2;
    if (y <= mid) return query(p << 1 | 0, x, y);
    if (x > mid) return query(p << 1 | 1, x, y);
    Node l = query(p << 1 | 0, x, y);
    Node r = query(p << 1 | 1, x, y);
    Node ret;
    merge(ret, l, r);
    return ret;
  }
} tree;
int rev_l[25], rev_r[25];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
  tree.init();
  scanf("%d", &m);
  while (m--) {
    int op, x, val, l, r, k, ans = 0;
    scanf("%d", &op);
    switch (op) {
      case 0:
        scanf("%d%d", &x, &val);
        tree.modify(1, x, val);
        break;
      case 1:
        scanf("%d%d%d", &l, &r, &k);
        for (int i = 1; i <= k; i++) {
          Node ret = tree.query(1, l, r);
          if (ret.maxsum.val == 0) {
            k = i - 1;
            break;
          }
          ans += ret.maxsum.val;
          tree.reverse(1, ret.maxsum.l, ret.maxsum.r);
          rev_l[i] = ret.maxsum.l;
          rev_r[i] = ret.maxsum.r;
        }
        for (int i = 1; i <= k; i++) tree.reverse(1, rev_l[i], rev_r[i]);
        printf("%d\n", ans);
        break;
    }
  }
  return 0;
}
