#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30, MAXN = 100110;
int a[MAXN], ansd, n, m, cmd, x, y, K;
bool ok;
struct date {
  int sum;
  int maxd, maxls, maxrs;
  int mind, minls, minrs;
  int mxpre, mipre, mxprep, miprep;
  int mxsuf, misuf, mxsufp, misufp;
  bool flag;
  void update(date* x, date* y) {
    sum = x->sum + y->sum;
    if (x->mxpre > y->mxpre + x->sum)
      mxpre = x->mxpre, mxprep = x->mxprep;
    else
      mxpre = x->sum + y->mxpre, mxprep = y->mxprep;
    if (x->mipre < y->mipre + x->sum)
      mipre = x->mipre, miprep = x->miprep;
    else
      mipre = x->sum + y->mipre, miprep = y->miprep;
    if (y->mxsuf > x->mxsuf + y->sum)
      mxsuf = y->mxsuf, mxsufp = y->mxsufp;
    else
      mxsuf = y->sum + x->mxsuf, mxsufp = x->mxsufp;
    if (y->misuf < x->misuf + y->sum)
      misuf = y->misuf, misufp = y->misufp;
    else
      misuf = y->sum + x->misuf, misufp = x->misufp;
    if (x->maxd > y->maxd)
      maxd = x->maxd, maxls = x->maxls, maxrs = x->maxrs;
    else
      maxd = y->maxd, maxls = y->maxls, maxrs = y->maxrs;
    if (x->mxsuf + y->mxpre > maxd)
      maxd = x->mxsuf + y->mxpre, maxls = x->mxsufp, maxrs = y->mxprep;
    if (x->mind < y->mind)
      mind = x->mind, minls = x->minls, minrs = x->minrs;
    else
      mind = y->mind, minls = y->minls, minrs = y->minrs;
    if (x->misuf + y->mipre < mind)
      mind = x->misuf + y->mipre, minls = x->misufp, minrs = y->miprep;
  }
  void rev() {
    flag ^= 1;
    swap(maxd, mind);
    swap(maxls, minls);
    swap(maxrs, minrs);
    swap(mxpre, mipre);
    swap(mxprep, miprep);
    swap(mxsuf, misuf);
    swap(mxsufp, misufp);
    maxd = -maxd, mind = -mind, mxpre = -mxpre, mipre = -mipre, mxsuf = -mxsuf,
    misuf = -misuf;
    sum = -sum;
  }
  void push(date* x, date* y) {
    if (flag) x->rev(), y->rev();
    flag = false;
  }
  void set(int pos, int d) {
    maxd = mind = sum = mxpre = mipre = mxsuf = misuf = d;
    maxls = maxrs = minls = minrs = mxprep = miprep = mxsufp = misufp = pos;
  }
} d[MAXN << 2];
void build(int x, int L, int R) {
  if (L == R) return (void)(d[x].set(L, a[L]));
  int mid = (L + R) >> 1;
  build(x << 1, L, mid);
  build(x << 1 | 1, mid + 1, R);
  d[x].update(&d[x << 1], &d[x << 1 | 1]);
}
void modify(int x, int L, int R, int pos, int dx) {
  if (L == R) return (void)(d[x].set(pos, dx));
  d[x].push(&d[x << 1], &d[x << 1 | 1]);
  int mid = (L + R) >> 1;
  if (pos <= mid)
    modify(x << 1, L, mid, pos, dx);
  else
    modify(x << 1 | 1, mid + 1, R, pos, dx);
  d[x].update(&d[x << 1], &d[x << 1 | 1]);
}
void evert(int x, int L, int R, int ls, int rs) {
  if (L > rs || R < ls) return;
  if (L >= ls && R <= rs) return (void)(d[x].rev());
  d[x].push(&d[x << 1], &d[x << 1 | 1]);
  int mid = (L + R) >> 1;
  evert(x << 1, L, mid, ls, rs);
  evert(x << 1 | 1, mid + 1, R, ls, rs);
  d[x].update(&d[x << 1], &d[x << 1 | 1]);
}
date ans, temp;
void query(int x, int L, int R, int ls, int rs) {
  if (L > rs || R < ls) return;
  if (L >= ls && R <= rs) {
    if (!ok) {
      ans = d[x];
      ok = 1;
      return;
    }
    temp = ans;
    ans.update(&temp, &d[x]);
    return;
  }
  d[x].push(&d[x << 1], &d[x << 1 | 1]);
  int mid = (L + R) >> 1;
  query(x << 1, L, mid, ls, rs);
  query(x << 1 | 1, mid + 1, R, ls, rs);
  d[x].update(&d[x << 1], &d[x << 1 | 1]);
}
struct line {
  int l, r;
  line(int l = 0, int r = 0) : l(l), r(r) {}
} id[30];
int pt;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  build(1, 1, n);
  cin >> m;
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d", &cmd, &x, &y);
    if (!cmd)
      modify(1, 1, n, x, y), a[x] = y;
    else {
      scanf("%d", &K);
      pt = 0;
      ansd = 0;
      for (; K; K--) {
        ok = 0;
        query(1, 1, n, x, y);
        if (ans.maxd <= 0) break;
        ansd += ans.maxd;
        evert(1, 1, n, ans.maxls, ans.maxrs);
        id[++pt] = line(ans.maxls, ans.maxrs);
      }
      printf("%d\n", ansd);
      for (; pt; pt--) evert(1, 1, n, id[pt].l, id[pt].r);
    }
  }
  return 0;
}
