#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int MAXK = 21;
int n, m, a[MAXN];
namespace SGT {
struct Node {
  int sumv;
  int maxpf, maxsf, maxsub;
  int minpf, minsf, minsub;
  int maxpfpos, maxsfpos, maxsubposl, maxsubposr;
  int minpfpos, minsfpos, minsubposl, minsubposr;
  bool oppo;
  void init(int p, int v) {
    sumv = v;
    maxpf = maxsf = maxsub = v;
    minpf = minsf = minsub = v;
    maxpfpos = maxsfpos = maxsubposl = maxsubposr = p;
    minpfpos = minsfpos = minsubposl = minsubposr = p;
    oppo = false;
  }
  void merge(const Node &l, const Node &r) {
    sumv = l.sumv + r.sumv;
    maxpf = max(l.maxpf, l.sumv + r.maxpf);
    maxsf = max(r.maxsf, r.sumv + l.maxsf);
    maxsub = max(l.maxsf + r.maxpf, max(l.maxsub, r.maxsub));
    minpf = min(l.minpf, l.sumv + r.minpf);
    minsf = min(r.minsf, r.sumv + l.minsf);
    minsub = min(l.minsf + r.minpf, min(l.minsub, r.minsub));
    maxpfpos = maxpf == l.maxpf ? l.maxpfpos : r.maxpfpos;
    maxsfpos = maxsf == r.maxsf ? r.maxsfpos : l.maxsfpos;
    if (maxsub == l.maxsub) {
      maxsubposl = l.maxsubposl;
      maxsubposr = l.maxsubposr;
    } else if (maxsub == r.maxsub) {
      maxsubposl = r.maxsubposl;
      maxsubposr = r.maxsubposr;
    } else {
      maxsubposl = l.maxsfpos;
      maxsubposr = r.maxpfpos;
    }
    minpfpos = minpf == l.minpf ? l.minpfpos : r.minpfpos;
    minsfpos = minsf == r.minsf ? r.minsfpos : l.minsfpos;
    if (minsub == l.minsub) {
      minsubposl = l.minsubposl;
      minsubposr = l.minsubposr;
    } else if (minsub == r.minsub) {
      minsubposl = r.minsubposl;
      minsubposr = r.minsubposr;
    } else {
      minsubposl = l.minsfpos;
      minsubposr = r.minpfpos;
    }
  }
  void do_oppo() {
    sumv = -sumv;
    swap(maxpf, minpf);
    swap(maxsf, minsf);
    swap(maxsub, minsub);
    maxpf = -maxpf, maxsf = -maxsf, maxsub = -maxsub;
    minpf = -minpf, minsf = -minsf, minsub = -minsub;
    swap(maxpfpos, minpfpos);
    swap(maxsfpos, minsfpos);
    swap(maxsubposl, minsubposl);
    swap(maxsubposr, minsubposr);
    oppo = !oppo;
  }
  void print(int l, int r) {
    printf("Info of range (%d, %d)\n", l, r);
    printf("sumv = %d\n", sumv);
    printf("maxpf = %d, maxsf = %d, maxsub = %d\n", maxpf, maxsf, maxsub);
    printf("minpf = %d, minsf = %d, minsub = %d\n", minpf, minsf, minsub);
    printf("maxpfpos = %d, maxsfpos = %d, maxsubposl = %d, maxsubposr = %d\n",
           maxpfpos, maxsfpos, maxsubposl, maxsubposr);
    printf("minpfpos = %d, minsfpos = %d, minsubposl = %d, minsubposr = %d\n",
           minpfpos, minsfpos, minsubposl, minsubposr);
    printf("oppo = %d\n", int(oppo));
  }
};
Node nod[MAXN << 2];
void maintain(int o, int L, int R) {
  if (L == R) return;
  int lc = o << 1, rc = lc | 1;
  nod[o].merge(nod[lc], nod[rc]);
}
void _build(int o, int L, int R) {
  if (L == R) {
    nod[o].init(L, a[L]);
    return;
  }
  int M = (L + R) / 2, lc = o << 1, rc = lc | 1;
  _build(lc, L, M), _build(rc, M + 1, R);
  maintain(o, L, R);
}
void build() { _build(1, 1, n); }
int left, right, val;
void pushdown(int o, int L, int R) {
  if (!nod[o].oppo) return;
  nod[o].oppo = false;
  if (L == R) return;
  int lc = o << 1, rc = lc | 1;
  nod[lc].do_oppo();
  nod[rc].do_oppo();
}
void _modify(int o, int L, int R) {
  pushdown(o, L, R);
  if (L == R) {
    nod[o].init(L, val);
    return;
  }
  int M = (L + R) / 2, lc = o << 1, rc = lc | 1;
  if (left <= M)
    _modify(lc, L, M);
  else
    _modify(rc, M + 1, R);
  maintain(o, L, R);
}
void modify(int p, int v) { left = p, val = v, _modify(1, 1, n); }
Node _query(int o, int L, int R) {
  pushdown(o, L, R);
  if (L >= left && R <= right) return nod[o];
  int M = (L + R) / 2, lc = o << 1, rc = lc | 1;
  if (right <= M)
    return _query(lc, L, M);
  else if (left > M)
    return _query(rc, M + 1, R);
  else {
    Node rtn;
    rtn.merge(_query(lc, L, M), _query(rc, M + 1, R));
    return rtn;
  }
}
Node query(int l, int r) {
  left = l, right = r;
  return _query(1, 1, n);
}
void _do_oppo(int o, int L, int R) {
  pushdown(o, L, R);
  if (L >= left && R <= right) {
    nod[o].do_oppo();
    return;
  }
  int M = (L + R) / 2, lc = o << 1, rc = lc | 1;
  if (left <= M) _do_oppo(lc, L, M);
  if (right > M) _do_oppo(rc, M + 1, R);
  maintain(o, L, R);
}
void do_oppo(int l, int r) { left = l, right = r, _do_oppo(1, 1, n); }
}  // namespace SGT
void input() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  SGT::build();
}
int stkl[MAXK], stkr[MAXK], top = 0;
void solve() {
  scanf("%d", &m);
  while (m--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 0) {
      int i, val;
      scanf("%d%d", &i, &val);
      SGT::modify(i, val);
    } else {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      int ans = 0, now = 0;
      while (k--) {
        SGT::Node nod = SGT::query(l, r);
        if (nod.maxsub <= 0) break;
        now += nod.maxsub;
        ans = max(ans, now);
        stkl[top] = nod.maxsubposl;
        stkr[top] = nod.maxsubposr;
        SGT::do_oppo(stkl[top], stkr[top]);
        ++top;
      }
      while (top--) SGT::do_oppo(stkl[top], stkr[top]);
      ++top;
      printf("%d\n", ans);
    }
  }
}
int main() {
  input(), solve();
  return 0;
}
