#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long llINF = 1e18;
const int MAXN = 1e5 + 5;
int n, Q;
int a[MAXN];
namespace SegmentTree {
struct Node {
  int lmax, rmax, lmin, rmin, maxl, maxr, minl, minr, sum, maxsum, minsum,
      maxposl, minposl, maxposr, minposr;
  Node(int pos = 0, int v = 0) {
    maxl = maxr = minl = minr = maxposl = maxposr = minposl = minposr = pos;
    lmax = rmax = lmin = rmin = sum = maxsum = minsum = v;
  }
  friend Node operator+(const Node &lhs, const Node &rhs) {
    Node res;
    if (lhs.lmax > lhs.sum + rhs.lmax)
      res.lmax = lhs.lmax, res.maxl = lhs.maxl;
    else
      res.lmax = lhs.sum + rhs.lmax, res.maxl = rhs.maxl;
    if (rhs.rmax > rhs.sum + lhs.rmax)
      res.rmax = rhs.rmax, res.maxr = rhs.maxr;
    else
      res.rmax = rhs.sum + lhs.rmax, res.maxr = lhs.maxr;
    if (lhs.lmin < lhs.sum + rhs.lmin)
      res.lmin = lhs.lmin, res.minl = lhs.minl;
    else
      res.lmin = lhs.sum + rhs.lmin, res.minl = rhs.minl;
    if (rhs.rmin < rhs.sum + lhs.rmin)
      res.rmin = rhs.rmin, res.minr = rhs.minr;
    else
      res.rmin = rhs.sum + lhs.rmin, res.minr = lhs.minr;
    res.sum = lhs.sum + rhs.sum;
    res.maxsum = lhs.rmax + rhs.lmax;
    res.maxposl = lhs.maxr;
    res.maxposr = rhs.maxl;
    if (res.maxsum < lhs.maxsum)
      res.maxsum = lhs.maxsum, res.maxposl = lhs.maxposl,
      res.maxposr = lhs.maxposr;
    if (res.maxsum < rhs.maxsum)
      res.maxsum = rhs.maxsum, res.maxposl = rhs.maxposl,
      res.maxposr = rhs.maxposr;
    res.minsum = lhs.rmin + rhs.lmin;
    res.minposl = lhs.minr;
    res.minposr = rhs.minl;
    if (res.minsum > lhs.minsum)
      res.minsum = lhs.minsum, res.minposl = lhs.minposl,
      res.minposr = lhs.minposr;
    if (res.minsum > rhs.minsum)
      res.minsum = rhs.minsum, res.minposl = rhs.minposl,
      res.minposr = rhs.minposr;
    return res;
  }
  void rev() {
    sum = -sum;
    swap(lmax, lmin);
    swap(maxl, minl);
    lmax = -lmax;
    lmin = -lmin;
    swap(rmax, rmin);
    swap(maxr, minr);
    rmax = -rmax;
    rmin = -rmin;
    swap(maxsum, minsum);
    swap(maxposl, minposl);
    swap(maxposr, minposr);
    maxsum = -maxsum;
    minsum = -minsum;
  }
};
struct Tree {
  int l, r;
  int tag;
  Node val;
} tree[MAXN << 2];
void update(int k) { tree[k].val = tree[k << 1].val + tree[k << 1 | 1].val; }
void apply(int k) {
  tree[k].tag ^= 1;
  tree[k].val.rev();
}
void down(int k) {
  if (tree[k].tag) {
    apply(k << 1);
    apply(k << 1 | 1);
    tree[k].tag = 0;
  }
}
void Build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;
  if (l == r) {
    tree[k].val = Node(l, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  Build(k << 1, l, mid);
  Build(k << 1 | 1, mid + 1, r);
  update(k);
}
void Modify(int k, int x, int v) {
  if (tree[k].l == tree[k].r) {
    tree[k].val = Node(tree[k].l, v);
    return;
  }
  down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (x <= mid)
    Modify(k << 1, x, v);
  else
    Modify(k << 1 | 1, x, v);
  update(k);
}
void Reverse(int k, int l, int r) {
  if (tree[k].l >= l && tree[k].r <= r) {
    apply(k);
    return;
  }
  down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (l <= mid) Reverse(k << 1, l, r);
  if (r > mid) Reverse(k << 1 | 1, l, r);
  update(k);
}
Node Query(int k, int l, int r) {
  if (tree[k].l >= l && tree[k].r <= r) return tree[k].val;
  down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid) return Query(k << 1, l, r);
  if (l > mid) return Query(k << 1 | 1, l, r);
  return Query(k << 1, l, r) + Query(k << 1 | 1, l, r);
}
}  // namespace SegmentTree
using SegmentTree::Node;
vector<Node> vec;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  SegmentTree::Build(1, 1, n);
  scanf("%d", &Q);
  while (Q--) {
    int op, l, r, k, x, ans;
    scanf("%d", &op);
    if (op == 0) {
      scanf("%d%d", &x, &k);
      SegmentTree::Modify(1, x, k);
    } else {
      scanf("%d%d%d", &l, &r, &k);
      vec.clear();
      ans = 0;
      for (int i = 1; i <= k; i++) {
        Node tmp = SegmentTree::Query(1, l, r);
        if (tmp.maxsum <= 0) break;
        SegmentTree::Reverse(1, tmp.maxposl, tmp.maxposr);
        vec.push_back(tmp);
        ans += tmp.maxsum;
      }
      for (auto x : vec) SegmentTree::Reverse(1, x.maxposl, x.maxposr);
      printf("%d\n", ans);
    }
  }
  return 0;
}
