#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n;
int a[maxn];
struct Pos {
  int l, r;
  Pos(int _l = 0, int _r = 0) {
    l = _l;
    r = _r;
  }
};
Pos merge(Pos a, Pos b, int size) {
  if (!b.l) return a;
  if (!a.l) return Pos(b.l + size, b.r + size);
  return Pos(a.l, b.r + size);
}
struct Node {
  Pos l[2], r[2], s[2];
  int ls[2], rs[2], ss[2], size, sum;
  Node operator+(const Node &x) const {
    Node c;
    c.ss[0] = c.ss[1] = 0;
    c.s[0] = c.s[1] = Pos(0, 0);
    c.ls[0] = ls[0];
    c.ls[1] = ls[1];
    c.rs[0] = x.rs[0];
    c.rs[1] = x.rs[1];
    c.l[0] = l[0];
    c.l[1] = l[1];
    c.r[0] = Pos(x.r[0].l + size, x.r[0].r + size);
    c.r[1] = Pos(x.r[1].l + size, x.r[1].r + size);
    c.sum = sum + x.sum;
    c.size = size + x.size;
    if (ss[1] > c.ss[1]) {
      c.ss[1] = ss[1];
      c.s[1] = s[1];
    }
    if (ss[0] < c.ss[0]) {
      c.ss[0] = ss[0];
      c.s[0] = s[0];
    }
    if (x.ss[1] > c.ss[1]) {
      c.ss[1] = x.ss[1];
      c.s[1] = Pos(x.s[1].l + size, x.s[1].r + size);
    }
    if (x.ss[0] < c.ss[0]) {
      c.ss[0] = x.ss[0];
      c.s[0] = Pos(x.s[0].l + size, x.s[0].r + size);
    }
    if (x.ls[1] + rs[1] > c.ss[1]) {
      c.ss[1] = rs[1] + x.ls[1];
      c.s[1] = merge(r[1], x.l[1], size);
    }
    if (x.ls[0] + rs[0] < c.ss[0]) {
      c.ss[0] = rs[0] + x.ls[0];
      c.s[0] = merge(r[0], x.l[0], size);
    }
    if (sum + x.ls[1] > c.ls[1]) {
      c.ls[1] = sum + x.ls[1];
      c.l[1] = merge(Pos(1, size), x.l[1], size);
    }
    if (sum + x.ls[0] < c.ls[0]) {
      c.ls[0] = sum + x.ls[0];
      c.l[0] = merge(Pos(1, size), x.l[0], size);
    }
    if (rs[1] + x.sum > c.rs[1]) {
      c.rs[1] = rs[1] + x.sum;
      c.r[1] = merge(r[1], Pos(1, x.size), size);
    }
    if (rs[0] + x.sum < c.rs[0]) {
      c.rs[0] = rs[0] + x.sum;
      c.r[0] = merge(r[0], Pos(1, x.size), size);
    }
    return c;
  }
};
Node init(int a) {
  Pos t(0, 0);
  Node c;
  c.sum = a;
  c.size = 1;
  c.l[0] = c.r[0] = c.l[1] = c.r[1] = c.s[0] = c.s[1] = t;
  c.ls[0] = c.rs[0] = c.ls[1] = c.rs[1] = c.ss[0] = c.ss[1] = 0;
  if (a > 0) {
    c.l[1] = c.r[1] = c.s[1] = Pos(1, 1);
    c.ls[1] = c.rs[1] = c.ss[1] = a;
  } else {
    c.l[0] = c.r[0] = c.s[0] = Pos(1, 1);
    c.ls[0] = c.rs[0] = c.ss[0] = a;
  }
  return c;
}
struct Segment {
  int root, p, son[maxn * 2][2], flag[maxn * 2];
  Node s[maxn * 2];
  void build(int &rt, int l, int r) {
    rt = ++p;
    if (l == r) {
      s[rt] = init(a[l]);
      return;
    }
    int mid = (l + r) >> 1;
    build(son[rt][0], l, mid);
    build(son[rt][1], mid + 1, r);
    s[rt] = s[son[rt][0]] + s[son[rt][1]];
  }
  void reverse(int a) {
    flag[a] ^= 1;
    swap(s[a].l[0], s[a].l[1]);
    swap(s[a].r[0], s[a].r[1]);
    swap(s[a].s[0], s[a].s[1]);
    swap(s[a].ls[0], s[a].ls[1]);
    swap(s[a].rs[0], s[a].rs[1]);
    swap(s[a].ss[0], s[a].ss[1]);
    s[a].ls[0] *= -1;
    s[a].rs[0] *= -1;
    s[a].ls[1] *= -1;
    s[a].rs[1] *= -1;
    s[a].ss[0] *= -1;
    s[a].ss[1] *= -1;
    s[a].sum *= -1;
  }
  void down(int a) {
    if (flag[a]) {
      reverse(son[a][0]);
      reverse(son[a][1]);
      flag[a] = 0;
    }
  }
  void change(int rt, int l, int r, int pos) {
    if (l == r) {
      s[rt] = init(a[pos]);
      return;
    }
    down(rt);
    int mid = (l + r) >> 1;
    if (pos > mid)
      change(son[rt][1], mid + 1, r, pos);
    else
      change(son[rt][0], l, mid, pos);
    s[rt] = s[son[rt][0]] + s[son[rt][1]];
  }
  Node query(int rt, int l, int r, int a, int b) {
    if (l == a && r == b) {
      return s[rt];
    }
    down(rt);
    int mid = (l + r) >> 1;
    Node ans;
    if (a > mid)
      ans = query(son[rt][1], mid + 1, r, a, b);
    else if (b <= mid)
      ans = query(son[rt][0], l, mid, a, b);
    else
      ans = query(son[rt][0], l, mid, a, mid) +
            query(son[rt][1], mid + 1, r, mid + 1, b);
    s[rt] = s[son[rt][0]] + s[son[rt][1]];
    return ans;
  }
  void Rev(int rt, int l, int r, int a, int b) {
    if (l == a && r == b) {
      reverse(rt);
      return;
    }
    down(rt);
    int mid = (l + r) >> 1;
    if (a > mid)
      Rev(son[rt][1], mid + 1, r, a, b);
    else if (b <= mid)
      Rev(son[rt][0], l, mid, a, b);
    else {
      Rev(son[rt][0], l, mid, a, mid);
      Rev(son[rt][1], mid + 1, r, mid + 1, b);
    }
    s[rt] = s[son[rt][0]] + s[son[rt][1]];
  }
  void write(int rt, int l, int r) {
    if (l == r) {
      printf("l=%d r=%d size=%d\n", l, r, s[rt].size);
      printf("big %d %d %d\n", s[rt].ss[1], s[rt].s[1].l, s[rt].s[1].r);
      printf("lbig %d %d %d\n", s[rt].ls[1], s[rt].l[1].l, s[rt].l[1].r);
      printf("rbig %d %d %d\n", s[rt].rs[1], s[rt].r[1].l, s[rt].r[1].r);
      return;
    }
    int mid = (l + r) >> 1;
    write(son[rt][0], l, mid);
    write(son[rt][1], mid + 1, r);
    printf("l=%d r=%d size=%d\n", l, r, s[rt].size);
    printf("big %d %d %d\n", s[rt].ss[1], s[rt].s[1].l, s[rt].s[1].r);
    printf("lbig %d %d %d\n", s[rt].ls[1], s[rt].l[1].l, s[rt].l[1].r);
    printf("rbig %d %d %d\n", s[rt].rs[1], s[rt].r[1].l, s[rt].r[1].r);
  }
} t;
int q;
Pos store[30];
void query() {
  int l, r, k, ans = 0;
  scanf("%d%d%d", &l, &r, &k);
  for (int i = 1; i <= k; i++) {
    Node get = t.query(t.root, 1, n, l, r);
    ans += get.ss[1];
    store[i] = get.s[1];
    if (store[i].l) t.Rev(t.root, 1, n, l - 1 + store[i].l, l - 1 + store[i].r);
  }
  printf("%d\n", ans);
  for (int i = 1; i <= k; i++) {
    if (store[i].l) t.Rev(t.root, 1, n, l + store[i].l - 1, l - 1 + store[i].r);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  t.build(t.root, 1, n);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int type;
    scanf("%d", &type);
    if (type == 0) {
      int g, v;
      scanf("%d%d", &g, &v);
      a[g] = v;
      t.change(t.root, 1, n, g);
    } else
      query();
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}
