#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &num) {
  num = 0;
  bool f = true;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = false;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    num = num * 10 + ch - '0';
    ch = getchar();
  }
  num = f ? num : -num;
}
int out[100];
template <class T>
inline void write(T x, char ch) {
  if (x == 0) {
    putchar('0');
    putchar(ch);
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  int num = 0;
  while (x) {
    out[num++] = (x % 10);
    x = x / 10;
  }
  for (int i = (num - 1); i >= (0); i--) putchar(out[i] + '0');
  putchar(ch);
}
const double eps = 1e-8;
struct Line {
  int l, r, v;
  Line(int _l = 0, int _r = 0, int _v = 0) : l(_l), r(_r), v(_v) {}
  inline bool operator<(const Line &k) const {
    if (v == k.v) return r < k.r;
    return v < k.v;
  }
  inline bool operator>(const Line &k) const {
    if (v == k.v) return r > k.r;
    return v > k.v;
  }
  inline Line operator+(const Line &b) const { return Line(l, b.r, v + b.v); }
};
inline Line Max(Line x, Line y) { return x < y ? y : x; }
inline Line Min(Line x, Line y) { return x > y ? y : x; }
struct Node {
  Line sum, pre, suf, cen, cem, prem, sufm;
  bool tag;
} tree[100005 * 4];
Line change[100005];
int n, m, k;
inline void input(int o, int l, int r, int x) {
  tree[o].sum = tree[o].pre = tree[o].suf = tree[o].prem = tree[o].sufm =
      tree[o].cen = tree[o].cem = Line(l, r, x);
  tree[o].tag = false;
}
inline Node updata(Node lc, Node rc) {
  Node o;
  if (lc.pre.l == 0) return rc;
  o.sum = lc.sum + rc.sum;
  o.pre = Max(lc.sum + rc.pre, lc.pre);
  o.suf = Max(lc.suf + rc.sum, rc.suf);
  o.prem = Min(lc.sum + rc.prem, lc.prem);
  o.sufm = Min(lc.sufm + rc.sum, rc.sufm);
  o.cen = Max(lc.pre, rc.suf);
  o.cen = Max(o.cen, Max(lc.cen, rc.cen));
  o.cen = Max(o.cen, lc.suf + rc.pre);
  o.cen = Max(o.cen, Max(o.pre, o.suf));
  o.cem = Min(lc.prem, rc.sufm);
  o.cem = Min(o.cem, Min(lc.cem, rc.cem));
  o.cem = Min(o.cem, Min(o.prem, o.sufm));
  o.cem = Min(o.cem, lc.sufm + rc.prem);
  o.tag = false;
  return o;
}
inline void F(Line &x) { x.v = -x.v; }
inline void rev(int o) {
  Node &x = tree[o];
  x.tag = !x.tag;
  swap(x.cen, x.cem);
  swap(x.pre, x.prem);
  swap(x.suf, x.sufm);
  F(x.cen);
  F(x.cem);
  F(x.pre);
  F(x.prem);
  F(x.suf);
  F(x.sufm);
  F(x.sum);
}
inline void pushdown(int o) {
  if (tree[o].tag) {
    rev(o << 1);
    rev((o << 1) | 1);
    tree[o].tag = false;
  }
}
void check(int o, int l, int r) {
  printf("root is :%d range is : %d %d \n", o, l, r);
  Node &x = tree[o];
  printf("tag :%d\n", x.tag ? 1 : 0);
  printf("sum is: %d %d %d ", x.sum.l, x.sum.r, x.sum.v);
  printf("cen is: %d %d %d ", x.cen.l, x.cen.r, x.cen.v);
  printf("cem is: %d %d %d ", x.cem.l, x.cem.r, x.cem.v);
  puts("");
  printf("pre is: %d %d %d ", x.pre.l, x.pre.r, x.pre.v);
  printf("prem is: %d %d %d ", x.prem.l, x.prem.r, x.prem.v);
  printf("suf is: %d %d %d ", x.suf.l, x.suf.r, x.suf.v);
  printf("sufm is: %d %d %d ", x.sufm.l, x.sufm.r, x.sufm.v);
  puts("");
  puts("");
  if (l == r) return;
  int mid = (((l) + (r)) >> 1), lc = (((o) + (0)) << 1), rc = lc | 1;
  check(lc, l, mid);
  check(rc, mid + 1, r);
}
inline Node query(int o, int l, int r, int L, int R) {
  if (L <= l && r <= R) return tree[o];
  pushdown(o);
  Node ret;
  int mid = (((l) + (r)) >> 1), lc = (((o) + (0)) << 1), rc = lc | 1;
  if (L <= mid) ret = updata(ret, query(lc, l, mid, L, R));
  if (R > mid) ret = updata(ret, query(rc, mid + 1, r, L, R));
  return ret;
}
inline void addtag(int o, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    rev(o);
    return;
  }
  pushdown(o);
  int mid = (((l) + (r)) >> 1), lc = (((o) + (0)) << 1), rc = lc | 1;
  if (L <= mid) addtag(lc, l, mid, L, R);
  if (R > mid) addtag(rc, mid + 1, r, L, R);
  tree[o] = updata(tree[lc], tree[rc]);
}
inline void modify(int o, int l, int r, int x, int y) {
  if (l == r) {
    input(o, l, r, y);
    return;
  }
  pushdown(o);
  int mid = (((l) + (r)) >> 1), lc = (((o) + (0)) << 1), rc = lc | 1;
  if (x <= mid)
    modify(lc, l, mid, x, y);
  else
    modify(rc, mid + 1, r, x, y);
  tree[o] = updata(tree[lc], tree[rc]);
}
inline void build(int o, int l, int r) {
  if (l == r) {
    int x;
    read(x);
    input(o, l, r, x);
    return;
  }
  int mid = (((l) + (r)) >> 1), lc = (((o) + (0)) << 1), rc = lc | 1;
  build(lc, l, mid);
  build(rc, mid + 1, r);
  tree[o] = updata(tree[lc], tree[rc]);
  tree[o].tag = false;
}
inline void init() {
  read(n);
  build(1, 1, n);
}
inline void work() {
  read(m);
  for (int i = (1); i <= (m); i++) {
    int op;
    read(op);
    switch (op) {
      case 0: {
        int x, y;
        read(x);
        read(y);
        modify(1, 1, n, x, y);
        break;
      }
      case 1: {
        int l, r, k, ans = 0, top = 0;
        read(l);
        read(r);
        read(k);
        while (k--) {
          Node x = query(1, 1, n, l, r);
          if (x.cen.v < 0) break;
          change[++top] = x.cen;
          addtag(1, 1, n, x.cen.l, x.cen.r);
          ans += x.cen.v;
        }
        for (int j = (1); j <= (top); j++)
          addtag(1, 1, n, change[j].l, change[j].r);
        write(ans, '\n');
      }
    }
  }
}
int main() {
  init();
  work();
}
