#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100010;
const int INF = 0x3f3f3f3f;
struct Data {
  int maxl, maxll, maxlr, maxr, maxrl, maxrr, maxs, maxsl, maxsr;
  int minl, minll, minlr, minr, minrl, minrr, mins, minsl, minsr;
  int sum, l, r;
};
inline void Flip(Data &a) {
  a.sum *= -1;
  a.maxl *= -1;
  a.minl *= -1;
  a.maxr *= -1;
  a.minr *= -1;
  a.maxs *= -1;
  a.mins *= -1;
  swap(a.maxl, a.minl);
  swap(a.maxll, a.minll);
  swap(a.maxlr, a.minlr);
  swap(a.maxr, a.minr);
  swap(a.maxrl, a.minrl);
  swap(a.maxrr, a.minrr);
  swap(a.maxs, a.mins);
  swap(a.maxsl, a.minsl);
  swap(a.maxsr, a.minsr);
}
inline void Modify(Data &c, int s) {
  c.sum = s;
  c.maxl = c.maxr = s = c.minl = c.minr = s;
  c.maxs = c.mins = 0;
  c.minrl = c.minrr = c.maxrl = c.maxrr = c.minll = c.minlr = c.maxll =
      c.maxlr = c.l;
  c.minsl = c.minsr = c.maxsl = c.maxsr = -1;
  if (s >= 0) c.maxs = s, c.maxsl = c.maxsr = c.l;
  if (s <= 0) c.mins = s, c.minsl = c.minsr = c.l;
}
inline Data Merge(const Data &l, const Data &r) {
  Data c;
  c.l = l.l;
  c.r = r.r;
  c.sum = l.sum + r.sum;
  c.maxl = c.minl = c.maxr = c.minr = c.sum;
  c.maxs = c.mins = 0;
  c.minll = c.minrl = c.maxll = c.maxrl = c.l;
  c.minsl = c.minsr = c.maxsl = c.maxsr = -1;
  c.minlr = c.minrr = c.maxrr = c.maxlr = c.r;
  if (l.mins < c.mins) c.mins = l.mins, c.minsl = l.minsl, c.minsr = l.minsr;
  if (l.maxs > c.maxs) c.maxs = l.maxs, c.maxsl = l.maxsl, c.maxsr = l.maxsr;
  if (r.mins < c.mins) c.mins = r.mins, c.minsl = r.minsl, c.minsr = r.minsr;
  if (r.maxs > c.maxs) c.maxs = r.maxs, c.maxsl = r.maxsl, c.maxsr = r.maxsr;
  if (l.minl < c.minl) c.minl = l.minl, c.minll = l.minll, c.minlr = l.minlr;
  if (l.maxl > c.maxl) c.maxl = l.maxl, c.maxll = l.maxll, c.maxlr = l.maxlr;
  if (r.minr < c.minr) c.minr = r.minr, c.minrl = r.minrl, c.minrr = r.minrr;
  if (r.maxr > c.maxr) c.maxr = r.maxr, c.maxrl = r.maxrl, c.maxrr = r.maxrr;
  if (l.sum + r.minl < c.minl)
    c.minl = l.sum + r.minl, c.minll = l.l, c.minlr = r.minlr;
  if (l.sum + r.maxl > c.maxl)
    c.maxl = l.sum + r.maxl, c.maxll = l.l, c.maxlr = r.maxlr;
  if (r.sum + l.minr < c.minr)
    c.minr = r.sum + l.minr, c.minrr = r.r, c.minrl = l.minrl;
  if (r.sum + l.maxr > c.maxr)
    c.maxr = r.sum + l.maxr, c.maxrr = r.r, c.maxrl = l.maxrl;
  if (l.minr + r.minl < c.mins)
    c.mins = l.minr + r.minl, c.minsl = l.minrl, c.minsr = r.minlr;
  if (l.maxr + r.maxl > c.maxs)
    c.maxs = l.maxr + r.maxl, c.maxsl = l.maxrl, c.maxsr = r.maxlr;
  return c;
}
struct Node {
  Data rec[2];
  int rev, l, r, time;
  Node *lc, *rc;
  void copy() { rec[1] = rec[0]; }
  void check(int _T) {
    if (time != _T) copy(), rev = 0, time = _T;
  }
  void update(int is_cp = 0, int _T = 0) {
    if (is_cp) check(_T), lc->check(_T), rc->check(_T);
    rec[is_cp] = Merge(lc->rec[is_cp], rc->rec[is_cp]);
  }
  void flip(int _T) {
    check(_T);
    rev ^= 1;
    Flip(rec[1]);
  }
  void sink(int _T) {
    check(_T);
    if (rev) {
      if (lc) lc->flip(time);
      if (rc) rc->flip(time);
      rev = 0;
    }
  }
  void modify(int s) { Modify(rec[0], s); }
} pool[MaxN << 2], *tail = pool, *rt;
int n, m;
int a[MaxN];
void build(int l, int r, Node *&rt) {
  rt = tail++;
  rt->rec[0].l = rt->l = l;
  rt->rec[0].r = rt->r = r;
  if (l == r) {
    rt->modify(a[l]);
    return;
  }
  int mid = l + r >> 1;
  build(l, mid, rt->lc);
  build(mid + 1, r, rt->rc);
  rt->update();
}
void modify(int pos, int x, Node *&rt) {
  if (rt->l == rt->r)
    rt->modify(x);
  else {
    int mid = rt->l + rt->r >> 1;
    if (pos <= mid)
      modify(pos, x, rt->lc);
    else
      modify(pos, x, rt->rc);
    rt->update();
  }
}
void flip(int l, int r, int time, Node *&rt) {
  if (rt->l >= l && rt->r <= r)
    rt->flip(time);
  else {
    int mid = rt->l + rt->r >> 1;
    rt->sink(time);
    if (l <= mid) flip(l, r, time, rt->lc);
    if (r > mid) flip(l, r, time, rt->rc);
    rt->update(1, time);
  }
}
Data query(int l, int r, int time, Node *&rt) {
  if (rt->l >= l && rt->r <= r) {
    rt->check(time);
    return rt->rec[1];
  } else {
    int mid = rt->l + rt->r >> 1;
    rt->sink(time);
    if (r <= mid)
      return query(l, r, time, rt->lc);
    else if (l > mid)
      return query(l, r, time, rt->rc);
    else
      return Merge(query(l, mid, time, rt->lc),
                   query(mid + 1, r, time, rt->rc));
  }
}
void print(Node *rt) {
  if (!rt) return;
  printf("[%d,%d] : ", rt->l, rt->r);
  printf("maxs=%d [%d,%d]\n", rt->rec[0].maxs, rt->rec[0].maxsl,
         rt->rec[0].maxsr);
  printf("mins=%d [%d,%d]\n", rt->rec[0].mins, rt->rec[0].minsl,
         rt->rec[0].minsr);
  printf("maxl=%d [%d,%d]\n", rt->rec[0].maxl, rt->rec[0].maxll,
         rt->rec[0].maxlr);
  printf("minl=%d [%d,%d]\n", rt->rec[0].minl, rt->rec[0].minll,
         rt->rec[0].minlr);
  printf("maxr=%d [%d,%d]\n", rt->rec[0].maxr, rt->rec[0].maxrl,
         rt->rec[0].maxrr);
  printf("minr=%d [%d,%d]\n", rt->rec[0].maxr, rt->rec[0].minrl,
         rt->rec[0].minrr);
  print(rt->lc);
  print(rt->rc);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, n, rt);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int op, l, r, k;
    scanf("%d%d%d", &op, &l, &r);
    if (!op)
      modify(l, r, rt);
    else {
      int res = 0;
      Data tmp;
      scanf("%d", &k);
      for (int j = 1; j <= k; j++) {
        tmp = query(l, r, i, rt);
        if (tmp.maxs <= 0) break;
        res += tmp.maxs;
        flip(tmp.maxsl, tmp.maxsr, i, rt);
      }
      printf("%d\n", res);
    }
  }
  return 0;
}
