#include <bits/stdc++.h>
using namespace std;
int a[100005];
struct data {
  int sval, lval, rval, sum, sl, sr, lr, rl;
  void init(bool type) {
    if (type)
      lval = rval = sval = -0x3f3f3f3f;
    else
      lval = rval = sval = +0x3f3f3f3f;
  }
  void reverse() {
    sval *= -1;
    lval *= -1;
    rval *= -1;
    sum *= -1;
  }
  void update(const data &l, const data &r, bool type) {
    sum = l.sum + r.sum;
    if (type)
      lval = max(l.lval, l.sum + r.lval), rval = max(r.rval, r.sum + l.rval),
      sval = max(max(l.sval, r.sval), l.rval + r.lval);
    else
      lval = min(l.lval, l.sum + r.lval), rval = min(r.rval, r.sum + l.rval),
      sval = min(min(l.sval, r.sval), l.rval + r.lval);
    if (l.lval == lval)
      lr = l.lr;
    else
      lr = r.lr;
    if (r.rval == rval)
      rl = r.rl;
    else
      rl = l.rl;
    if (l.sval == sval)
      sl = l.sl, sr = l.sr;
    else if (r.sval == sval)
      sl = r.sl, sr = r.sr;
    else
      sl = l.rl, sr = r.lr;
  }
};
struct info {
  data maxi, mini;
  void init() {
    maxi.init(1);
    mini.init(0);
  }
};
struct SGT {
  bool lazy[100005 << 1];
  int lson[100005 << 1], rson[100005 << 1], rt, sz;
  info node[100005 << 1];
  void init() {
    rt = sz = 0;
    memset(lazy, 0, sizeof(lazy));
    memset(lson, 0, sizeof(lson));
    memset(rson, 0, sizeof(rson));
    for (int i = 0; i < (100005 << 1); i++) node[i].init();
  }
  void pushup(info &now, const info &l, const info &r) {
    now.maxi.update(l.maxi, r.maxi, 1);
    now.mini.update(l.mini, r.mini, 0);
  }
  void pushdown(int u) {
    node[lson[u]].maxi.reverse();
    node[lson[u]].mini.reverse();
    node[rson[u]].maxi.reverse();
    node[rson[u]].mini.reverse();
    swap(node[lson[u]].maxi, node[lson[u]].mini);
    swap(node[rson[u]].maxi, node[rson[u]].mini);
    lazy[u] ^= 1;
    lazy[lson[u]] ^= 1;
    lazy[rson[u]] ^= 1;
  }
  void build(int &u, int l, int r) {
    u = ++sz;
    if (l == r) {
      node[u].maxi = (data){a[l], a[l], a[l], a[l], l, r, r, l};
      node[u].mini = (data){a[l], a[l], a[l], a[l], l, r, r, l};
      return;
    }
    int mid = (l + r) >> 1;
    build(lson[u], l, mid);
    build(rson[u], mid + 1, r);
    pushup(node[u], node[lson[u]], node[rson[u]]);
  }
  void modify(int u, int l, int r, int p) {
    if (l == r) {
      node[u].maxi = (data){a[l], a[l], a[l], a[l], l, r, r, l};
      node[u].mini = (data){a[l], a[l], a[l], a[l], l, r, r, l};
      return;
    }
    if (lazy[u]) pushdown(u);
    int mid = (l + r) >> 1;
    if (p <= mid)
      modify(lson[u], l, mid, p);
    else
      modify(rson[u], mid + 1, r, p);
    pushup(node[u], node[lson[u]], node[rson[u]]);
  }
  void modify(int u, int l, int r, int al, int ar) {
    if (al <= l && r <= ar) {
      node[u].maxi.reverse();
      node[u].mini.reverse();
      swap(node[u].maxi, node[u].mini);
      lazy[u] ^= 1;
      return;
    }
    if (lazy[u]) pushdown(u);
    int mid = (l + r) >> 1;
    if (al <= mid) modify(lson[u], l, mid, al, ar);
    if (mid < ar) modify(rson[u], mid + 1, r, al, ar);
    pushup(node[u], node[lson[u]], node[rson[u]]);
  }
  info query(int u, int l, int r, int al, int ar) {
    if (al <= l && r <= ar) return node[u];
    info now, lnode, rnode;
    now.init();
    lnode.init();
    rnode.init();
    if (lazy[u]) pushdown(u);
    int mid = (l + r) >> 1;
    if (al <= mid) lnode = query(lson[u], l, mid, al, ar);
    if (mid < ar) rnode = query(rson[u], mid + 1, r, al, ar);
    if (mid < al)
      now = rnode;
    else if (ar <= mid)
      now = lnode;
    else
      pushup(now, lnode, rnode);
    return now;
  }
} T1;
int N, M, ans;
void dfs(int k, int l, int r) {
  info now = T1.query(T1.rt, 1, N, l, r);
  if (now.maxi.sval <= 0) return;
  ans += now.maxi.sval;
  T1.modify(T1.rt, 1, N, now.maxi.sl, now.maxi.sr);
  if (k - 1) dfs(k - 1, l, r);
  T1.modify(T1.rt, 1, N, now.maxi.sl, now.maxi.sr);
}
int main() {
  scanf("%d", &N);
  T1.init();
  for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
  T1.build(T1.rt, 1, N);
  scanf("%d", &M);
  for (int i = 1, c, l, r, k; i <= M; i++) {
    scanf("%d", &c);
    if (!c) {
      scanf("%d", &k);
      scanf("%d", &a[k]);
      T1.modify(T1.rt, 1, N, k);
    } else {
      scanf("%d%d%d", &l, &r, &k);
      ans = 0;
      dfs(k, l, r);
      printf("%d\n", ans);
    }
  }
  return 0;
}
