#include <bits/stdc++.h>
template <typename Tp>
void in(Tp &x) {
  char ch = getchar(), f = 1;
  x = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
template <typename Tp>
bool chkmax(Tp &x, Tp y) {
  return x > y ? 0 : (x = y, 1);
}
template <typename Tp>
bool chkmin(Tp &x, Tp y) {
  return x < y ? 0 : (x = y, 1);
}
template <typename Tp>
Tp Max(Tp x, Tp y) {
  return x > y ? x : y;
}
template <typename Tp>
Tp Min(Tp x, Tp y) {
  return x < y ? x : y;
}
const int MAXN = 400010;
int n, m, num[MAXN], order[MAXN][2];
struct Tag {
  bool fu;
  Tag(bool t = false) : fu(t) {}
};
struct Segment {
  Tag tag;
  int sum;
  int maxv, maxl, maxr;
  int minv, minl, minr;
  int maxlv, maxlp, maxrv, maxrp;
  int minlv, minlp, minrv, minrp;
  void Fu();
  Segment operator+(const Segment &another) const;
} data[MAXN];
void Segment::Fu() {
  sum = -sum;
  maxv ^= minv ^= maxv ^= minv;
  maxl ^= minl ^= maxl ^= minl;
  maxr ^= minr ^= maxr ^= minr;
  maxlv ^= minlv ^= maxlv ^= minlv;
  maxlp ^= minlp ^= maxlp ^= minlp;
  maxrv ^= minrv ^= maxrv ^= minrv;
  maxrp ^= minrp ^= maxrp ^= minrp;
  maxv = -maxv;
  minv = -minv;
  maxlv = -maxlv;
  minlv = -minlv;
  maxrv = -maxrv;
  minrv = -minrv;
  tag.fu ^= 1;
}
void pushdown(int nums) {
  if (data[nums].tag.fu) {
    data[nums].tag.fu = false;
    data[nums << 1].Fu();
    data[nums << 1 | 1].Fu();
  }
}
Segment Segment::operator+(const Segment &another) const {
  Segment ret;
  ret.sum = sum + another.sum;
  ret.maxv = maxv;
  ret.maxl = maxl;
  ret.maxr = maxr;
  ret.minv = minv;
  ret.minl = minl;
  ret.minr = minr;
  if (chkmax(ret.maxv, another.maxv))
    ret.maxl = another.maxl, ret.maxr = another.maxr;
  if (chkmin(ret.minv, another.minv))
    ret.minl = another.minl, ret.minr = another.minr;
  if (chkmax(ret.maxv, maxrv + another.maxlv))
    ret.maxl = maxrp, ret.maxr = another.maxlp;
  if (chkmin(ret.minv, minrv + another.minlv))
    ret.minl = minrp, ret.minr = another.minlp;
  ret.maxlv = maxlv;
  ret.maxlp = maxlp;
  if (chkmax(ret.maxlv, sum + another.maxlv)) ret.maxlp = another.maxlp;
  ret.maxrv = another.maxrv;
  ret.maxrp = another.maxrp;
  if (chkmax(ret.maxrv, another.sum + maxrv)) ret.maxrp = maxrp;
  ret.minlv = minlv;
  ret.minlp = minlp;
  if (chkmin(ret.minlv, sum + another.minlv)) ret.minlp = another.minlp;
  ret.minrv = another.minrv;
  ret.minrp = another.minrp;
  if (chkmin(ret.minrv, another.sum + minrv)) ret.minrp = minrp;
  return ret;
}
void build_tree(int l, int r, int now) {
  if (l == r) {
    data[now].sum = num[l];
    data[now].maxv = num[l];
    data[now].maxl = data[now].maxr = l;
    data[now].minv = num[l];
    data[now].minl = data[now].minr = l;
    data[now].maxlv = num[l];
    data[now].maxlp = l;
    data[now].maxrv = num[l];
    data[now].maxrp = l;
    data[now].minlv = num[l];
    data[now].minlp = l;
    data[now].minrv = num[l];
    data[now].minrp = l;
  } else {
    int mid = (l + r) >> 1;
    build_tree(l, mid, now << 1);
    build_tree(mid + 1, r, now << 1 | 1);
    data[now] = data[now << 1] + data[now << 1 | 1];
  }
}
void change(int now, int l, int r, int pos, int d) {
  if (l == r) {
    num[l] = d;
    data[now].sum = num[l];
    data[now].maxv = num[l];
    data[now].maxl = data[now].maxr = l;
    data[now].minv = num[l];
    data[now].minl = data[now].minr = l;
    data[now].maxlv = num[l];
    data[now].maxlp = l;
    data[now].maxrv = num[l];
    data[now].maxrp = l;
    data[now].minlv = num[l];
    data[now].minlp = l;
    data[now].minrv = num[l];
    data[now].minrp = l;
  } else {
    pushdown(now);
    int mid = (l + r) >> 1;
    if (pos <= mid)
      change(now << 1, l, mid, pos, d);
    else
      change(now << 1 | 1, mid + 1, r, pos, d);
    data[now] = data[now << 1] + data[now << 1 | 1];
  }
}
Segment query(int now, int l, int r, int x, int y) {
  if (x <= l && r <= y) return data[now];
  pushdown(now);
  int mid = (l + r) >> 1;
  if (y <= mid) return query(now << 1, l, mid, x, y);
  if (mid < x) return query(now << 1 | 1, mid + 1, r, x, y);
  return query(now << 1, l, mid, x, y) + query(now << 1 | 1, mid + 1, r, x, y);
}
void getfan(int now, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    data[now].Fu();
    return;
  }
  pushdown(now);
  int mid = (l + r) >> 1;
  if (x <= mid) getfan(now << 1, l, mid, x, y);
  if (mid < y) getfan(now << 1 | 1, mid + 1, r, x, y);
  data[now] = data[now << 1] + data[now << 1 | 1];
}
int main() {
  in(n);
  for (int i = (1), i_END_ = (n); i <= i_END_; i++) in(num[i]);
  build_tree(1, n, 1);
  in(m);
  while (m--) {
    int tp;
    in(tp);
    if (!tp) {
      int x, y;
      in(x);
      in(y);
      change(1, 1, n, x, y);
    } else {
      order[0][0] = 0;
      int l, r, k;
      in(l);
      in(r);
      in(k);
      int ans = 0;
      for (int i = (1), i_END_ = (k); i <= i_END_; i++) {
        Segment mx = query(1, 1, n, l, r);
        if (mx.maxv < 0) break;
        ans += mx.maxv;
        int ml = mx.maxl;
        int mr = mx.maxr;
        getfan(1, 1, n, ml, mr);
        order[++order[0][0]][0] = ml;
        order[order[0][0]][1] = mr;
      }
      printf("%d\n", ans);
      for (int i = (order[0][0]), i_END_ = (1); i >= i_END_; i--) {
        getfan(1, 1, n, order[i][0], order[i][1]);
      }
    }
  }
  return 0;
}
