#include <bits/stdc++.h>
using namespace std;
int n, k, a[100010], tag[800010], q, op, opx, opy, opz, top, opedx[100],
    opedy[100];
int ans, realans;
struct node {
  int sum;
  int lmax, rmax, smax;
  int lxp, rxp, slxp, srxp;
} nodes[800010][2], emp, ret;
bool flag;
node merge(node one, node ano) {
  node res = emp;
  res.sum = one.sum + ano.sum;
  if (one.lmax > one.sum + ano.lmax) {
    res.lmax = one.lmax;
    res.lxp = one.lxp;
  } else {
    res.lmax = one.sum + ano.lmax;
    res.lxp = ano.lxp;
  }
  if (ano.rmax > ano.sum + one.rmax) {
    res.rmax = ano.rmax;
    res.rxp = ano.rxp;
  } else {
    res.rmax = ano.sum + one.rmax;
    res.rxp = one.rxp;
  }
  res.smax = -5e8;
  if (one.smax > res.smax) {
    res.smax = one.smax;
    res.slxp = one.slxp;
    res.srxp = one.srxp;
  }
  if (ano.smax > res.smax) {
    res.smax = ano.smax;
    res.slxp = ano.slxp;
    res.srxp = ano.srxp;
  }
  if (one.rmax + ano.lmax > res.smax) {
    res.smax = one.rmax + ano.lmax;
    res.slxp = one.rxp;
    res.srxp = ano.lxp;
  }
  return res;
}
void build(int l, int r, int x) {
  if (l ^ r) {
    int mid = (l + r) >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    nodes[x][0] = merge(nodes[x << 1][0], nodes[x << 1 | 1][0]);
    nodes[x][1] = merge(nodes[x << 1][1], nodes[x << 1 | 1][1]);
  } else {
    nodes[x][0].lmax = nodes[x][0].rmax = nodes[x][0].smax = nodes[x][0].sum =
        a[l];
    nodes[x][1].lxp = nodes[x][1].rxp = nodes[x][1].slxp = nodes[x][1].srxp =
        nodes[x][0].lxp = nodes[x][0].rxp = nodes[x][0].slxp =
            nodes[x][0].srxp = l;
    nodes[x][1].lmax = nodes[x][1].rmax = nodes[x][1].smax = nodes[x][1].sum =
        -a[l];
  }
}
void pushdown(int x) {
  if (tag[x]) {
    tag[x << 1] ^= 1;
    tag[x << 1 | 1] ^= 1;
    swap(nodes[x][0], nodes[x][1]);
    tag[x] = 0;
  }
}
void update(int l, int r, int x, int fr, int ba) {
  if (l > ba || r < fr) return;
  if (l >= fr && r <= ba)
    tag[x] ^= 1;
  else {
    pushdown(x);
    int mid = (l + r) >> 1;
    update(l, mid, x << 1, fr, ba);
    update(mid + 1, r, x << 1 | 1, fr, ba);
    pushdown(x << 1);
    pushdown(x << 1 | 1);
    nodes[x][0] = merge(nodes[x << 1][0], nodes[x << 1 | 1][0]);
    nodes[x][1] = merge(nodes[x << 1][1], nodes[x << 1 | 1][1]);
  }
}
void ins(int l, int r, int x, int pos, int val) {
  pushdown(x);
  if (l ^ r) {
    int mid = (l + r) >> 1;
    if (pos <= mid)
      ins(l, mid, x << 1, pos, val);
    else
      ins(mid + 1, r, x << 1 | 1, pos, val);
    pushdown(x << 1);
    pushdown(x << 1 | 1);
    nodes[x][0] = merge(nodes[x << 1][0], nodes[x << 1 | 1][0]);
    nodes[x][1] = merge(nodes[x << 1][1], nodes[x << 1 | 1][1]);
  } else {
    nodes[x][0].lmax = nodes[x][0].rmax = nodes[x][0].smax = nodes[x][0].sum =
        val;
    nodes[x][1].lmax = nodes[x][1].rmax = nodes[x][1].smax = nodes[x][1].sum =
        -val;
  }
}
void findnode(int l, int r, int x, int fr, int ba) {
  if (l > ba || r < fr) return;
  pushdown(x);
  if (l >= fr && r <= ba) {
    if (flag)
      ret = merge(ret, nodes[x][0]);
    else {
      ret = nodes[x][0];
      flag = 1;
    }
  } else {
    int mid = (l + r) >> 1;
    findnode(l, mid, x << 1, fr, ba);
    findnode(mid + 1, r, x << 1 | 1, fr, ba);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  scanf("%d", &q);
  build(1, n, 1);
  while (q--) {
    scanf("%d", &op);
    if (op) {
      scanf("%d %d %d", &opx, &opy, &opz);
      realans = ans = 0;
      for (int i = 1; i <= opz; ++i) {
        flag = 0;
        findnode(1, n, 1, opx, opy);
        int opl = ret.slxp;
        int opr = ret.srxp;
        ans += ret.smax;
        realans = max(realans, ans);
        update(1, n, 1, opl, opr);
        opedx[++top] = opl;
        opedy[top] = opr;
      }
      while (top) {
        update(1, n, 1, opedx[top], opedy[top]);
        --top;
      }
      printf("%d\n", realans);
    } else {
      scanf("%d %d", &opx, &opy);
      ins(1, n, 1, opx, opy);
    }
  }
  return 0;
}
