#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxm = 1e5 + 5;
char buf[1 << 21], *p1 = buf, *p2 = buf;
template <typename T>
inline void read(T &x) {
  x = 0;
  T f = 1;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - '0';
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  x *= f;
}
int n, m, a[maxn];
struct sec {
  int val, l, r;
  sec(int val, int l, int r) : val(val), l(l), r(r){};
  sec() {}
  inline bool operator<(const sec &T) const { return val < T.val; }
};
struct node {
  int l, r, sum;
  sec Max, lmax, rmax;
  sec Min, lmin, rmin;
  bool lazy;
  node(int l, int r, int sum)
      : l(l),
        r(r),
        sum(sum),
        Max(sec(sum, l, r)),
        lmax(sec(sum, l, r)),
        rmax(sec(sum, l, r)),
        Min(sec(sum, l, r)),
        lmin(sec(sum, l, r)),
        rmin(sec(sum, l, r)),
        lazy(false) {}
  node() {}
  inline node operator+(const node &T) const {
    node res(l, T.r, sum + T.sum);
    res.Max =
        max(max(Max, T.Max), sec(rmax.val + T.lmax.val, rmax.l, T.lmax.r));
    res.lmax = max(lmax, sec(sum + T.lmax.val, l, T.lmax.r));
    res.rmax = max(T.rmax, sec(rmax.val + T.sum, rmax.l, r));
    res.Min =
        min(min(Min, T.Min), sec(rmin.val + T.lmin.val, rmin.l, T.lmin.r));
    res.lmin = min(lmin, sec(sum + T.lmin.val, l, T.lmin.r));
    res.rmin = min(T.rmin, sec(rmin.val + T.sum, rmin.l, r));
    return res;
  }
} tree[maxn << 2];
inline void reverse(int p) {
  tree[p].sum = -tree[p].sum;
  swap(tree[p].Max, tree[p].Min);
  tree[p].Max.val = -tree[p].Max.val;
  tree[p].Min.val = -tree[p].Min.val;
  swap(tree[p].lmax, tree[p].lmin);
  tree[p].lmax.val = -tree[p].lmax.val;
  tree[p].lmin.val = -tree[p].lmin.val;
  swap(tree[p].rmax, tree[p].rmin);
  tree[p].rmax.val = -tree[p].rmax.val;
  tree[p].rmin.val = -tree[p].rmin.val;
  tree[p].lazy ^= 1;
}
inline void push_down(int p) {
  if (!tree[p].lazy) return;
  reverse((p << 1));
  reverse((p << 1 | 1));
  tree[p].lazy ^= 1;
}
inline void build(int p, int l, int r) {
  tree[p] = node(l, r, 0);
  if (l == r) return tree[p] = node(l, r, a[l]), void();
  int mid = (l + r) >> 1;
  build((p << 1), l, mid);
  build((p << 1 | 1), mid + 1, r);
  tree[p] = tree[(p << 1)] + tree[(p << 1 | 1)];
}
inline void modify_point(int p, int ps, int d) {
  int l = tree[p].l, r = tree[p].r;
  if (l == r) return tree[p] = node(l, r, d), void();
  push_down(p);
  int mid = (l + r) >> 1;
  if (ps <= mid)
    modify_point((p << 1), ps, d);
  else
    modify_point((p << 1 | 1), ps, d);
  tree[p] = tree[(p << 1)] + tree[(p << 1 | 1)];
}
inline void modify_reverse(int p, int L, int R) {
  int l = tree[p].l, r = tree[p].r;
  if (L <= l && r <= R) return reverse(p), void();
  push_down(p);
  int mid = (l + r) >> 1;
  if (L <= mid) modify_reverse((p << 1), L, R);
  if (R > mid) modify_reverse((p << 1 | 1), L, R);
  tree[p] = tree[(p << 1)] + tree[(p << 1 | 1)];
}
inline node query(int p, int L, int R) {
  int l = tree[p].l, r = tree[p].r;
  if (L <= l && r <= R) return tree[p];
  push_down(p);
  int mid = (l + r) >> 1;
  if (R <= mid)
    return query((p << 1), L, R);
  else if (L > mid)
    return query((p << 1 | 1), L, R);
  else
    return query((p << 1), L, R) + query((p << 1 | 1), L, R);
}
int main() {
  read(n);
  for (int i = 1; i <= n; ++i) read(a[i]);
  build(1, 1, n);
  read(m);
  int opt, l, r, k;
  while (m--) {
    read(opt), read(l), read(r);
    if (!opt)
      modify_point(1, l, r);
    else {
      read(k);
      int ans(0);
      static sec st[25];
      int top(0);
      while (k--) {
        sec res(query(1, l, r).Max);
        if (res.val <= 0) break;
        ans += res.val;
        modify_reverse(1, res.l, res.r);
        st[++top] = res;
      }
      printf("%d\n", ans);
      while (top) {
        modify_reverse(1, st[top].l, st[top].r);
        --top;
      }
    }
  }
  return 0;
}
