#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
int n, m, a[maxn];
struct node {
  int sum, maxv, maxl, maxr, minv, minl, minr, lmax, lmaxid, rmax, rmaxid, lmin,
      lminid, rmin, rminid;
  bool rev;
  inline void init(int pos, int val) {
    maxl = maxr = minl = minr = lmaxid = rmaxid = lminid = rminid = pos;
    sum = maxv = minv = lmax = rmax = lmin = rmin = val;
    rev = 0;
  }
  inline void pushtag() {
    sum = -sum;
    lmax = -lmax;
    rmax = -rmax;
    lmin = -lmin;
    rmin = -rmin;
    maxv = -maxv;
    minv = -minv;
    swap(lmax, lmin);
    swap(lmaxid, lminid);
    swap(rmax, rmin);
    swap(rmaxid, rminid);
    swap(maxv, minv);
    swap(maxl, minl);
    swap(maxr, minr);
    rev ^= 1;
  }
} t[maxn << 2], q[30];
inline node operator+(const node &a, const node &b) {
  node c;
  c.sum = a.sum + b.sum;
  c.lmax = a.lmax;
  c.lmaxid = a.lmaxid;
  c.lmin = a.lmin;
  c.lminid = a.lminid;
  c.rmax = b.rmax;
  c.rmaxid = b.rmaxid;
  c.rmin = b.rmin;
  c.rminid = b.rminid;
  if (a.sum + b.lmax > c.lmax) c.lmax = a.sum + b.lmax, c.lmaxid = b.lmaxid;
  if (a.sum + b.lmin < c.lmin) c.lmin = a.sum + b.lmin, c.lminid = b.lminid;
  if (a.rmax + b.sum > c.rmax) c.rmax = a.rmax + b.sum, c.rmaxid = a.rmaxid;
  if (a.rmin + b.sum < c.rmin) c.rmin = a.rmin + b.sum, c.rminid = a.rminid;
  if (a.maxv > b.maxv)
    c.maxv = a.maxv, c.maxl = a.maxl, c.maxr = a.maxr;
  else
    c.maxv = b.maxv, c.maxl = b.maxl, c.maxr = b.maxr;
  if (a.minv < b.minv)
    c.minv = a.minv, c.minl = a.minl, c.minr = a.minr;
  else
    c.minv = b.minv, c.minl = b.minl, c.minr = b.minr;
  if (a.rmax + b.lmax > c.maxv)
    c.maxv = a.rmax + b.lmax, c.maxl = a.rmaxid, c.maxr = b.lmaxid;
  if (a.rmin + b.lmin < c.minv)
    c.minv = a.rmin + b.lmin, c.minl = a.rminid, c.minr = b.lminid;
  c.rev = 0;
  return c;
}
inline void pushup(int x) { t[x] = t[(x << 1)] + t[(x << 1 | 1)]; }
inline void pushdown(int x) {
  if (t[x].rev) {
    t[(x << 1)].pushtag();
    t[(x << 1 | 1)].pushtag();
    t[x].rev = 0;
  }
}
void build(int l, int r, int x) {
  if (l == r) {
    t[x].init(l, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, (x << 1));
  build(mid + 1, r, (x << 1 | 1));
  pushup(x);
}
void update(int pos, int val, int l, int r, int x) {
  if (l == r) {
    t[x].init(pos, val);
    return;
  }
  pushdown(x);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(pos, val, l, mid, (x << 1));
  else
    update(pos, val, mid + 1, r, (x << 1 | 1));
  pushup(x);
}
void modify(int L, int R, int l, int r, int x) {
  if (L <= l && r <= R) {
    t[x].pushtag();
    return;
  }
  pushdown(x);
  int mid = (l + r) >> 1;
  if (L <= mid) modify(L, R, l, mid, (x << 1));
  if (R > mid) modify(L, R, mid + 1, r, (x << 1 | 1));
  pushup(x);
}
node query(int L, int R, int l, int r, int x) {
  if (L <= l && r <= R) return t[x];
  pushdown(x);
  int mid = (l + r) >> 1;
  if (R <= mid) return query(L, R, l, mid, (x << 1));
  if (L > mid) return query(L, R, mid + 1, r, (x << 1 | 1));
  return query(L, R, l, mid, (x << 1)) + query(L, R, mid + 1, r, (x << 1 | 1));
}
int main() {
  int i, op, l, r, k, x, y, ans;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, n, 1);
  scanf("%d", &m);
  while (m--) {
    scanf("%d", &op);
    if (op == 0) {
      scanf("%d%d", &x, &y);
      update(x, y, 1, n, 1);
    } else {
      scanf("%d%d%d", &l, &r, &k);
      ans = 0;
      for (i = 1; i <= k; i++) {
        q[i] = query(l, r, 1, n, 1);
        if (q[i].maxv <= 0) break;
        ans += q[i].maxv;
        modify(q[i].maxl, q[i].maxr, 1, n, 1);
      }
      while (--i) modify(q[i].maxl, q[i].maxr, 1, n, 1);
      printf("%d\n", ans);
    }
  }
  return 0;
}
