#include <bits/stdc++.h>
using namespace std;
const int maxn = 100015;
int n, m, x, op, y, k;
struct Q {
  int l, r, s;
};
Q operator+(Q a, Q b) { return (Q){a.l, b.r, a.s + b.s}; }
bool operator<(Q a, Q b) { return a.s < b.s; }
struct node {
  Q smax, smin, lmax, rmax, lmin, rmin, sum;
  int rev;
} t[maxn << 2];
queue<node> q;
void neww(int p, int l, int k) {
  t[p].smax = t[p].smin = t[p].lmax = t[p].rmax = t[p].lmin = t[p].rmin =
      t[p].sum = (Q){l, l, k};
}
node merge(node x, node y) {
  node z;
  z.smax = max(x.smax, y.smax);
  z.smax = max(z.smax, x.rmax + y.lmax);
  z.smin = min(x.smin, y.smin);
  z.smin = min(z.smin, x.rmin + y.lmin);
  z.lmax = max(x.lmax, x.sum + y.lmax);
  z.rmax = max(y.rmax, x.rmax + y.sum);
  z.lmin = min(x.lmin, x.sum + y.lmin);
  z.rmin = min(y.rmin, x.rmin + y.sum);
  z.sum = x.sum + y.sum;
  z.rev = 0;
  return z;
}
void pushdown(int o) {
  swap(t[o].smax, t[o].smin);
  swap(t[o].lmax, t[o].lmin);
  swap(t[o].rmax, t[o].rmin);
  t[o].smax.s *= -1, t[o].smin.s *= -1, t[o].lmax.s *= -1, t[o].rmax.s *= -1,
      t[o].lmin.s *= -1, t[o].rmin.s *= -1, t[o].sum.s *= -1;
  t[o].rev ^= 1;
}
void change(int o, int l, int r, int x, int k) {
  if (l == r) {
    neww(o, l, k);
    return;
  }
  int mid = (l + r) >> 1;
  if (t[o].rev) {
    pushdown(o << 1);
    pushdown(o << 1 | 1);
    t[o].rev ^= 1;
  }
  if (x <= mid)
    change(o * 2, l, mid, x, k);
  else
    change(o * 2 + 1, mid + 1, r, x, k);
  t[o] = merge(t[o * 2], t[o * 2 + 1]);
}
void rev(int o, int l, int r, int x, int y) {
  if ((l == x) && (r == y)) {
    pushdown(o);
    return;
  }
  int mid = (l + r) >> 1;
  if (t[o].rev) {
    pushdown(o << 1);
    pushdown(o << 1 | 1);
    t[o].rev ^= 1;
  }
  if (y <= mid)
    rev(o << 1, l, mid, x, y);
  else if (x > mid)
    rev(o << 1 | 1, mid + 1, r, x, y);
  else {
    rev(o << 1, l, mid, x, mid);
    rev(o << 1 | 1, mid + 1, r, mid + 1, y);
  }
  t[o] = merge(t[o << 1], t[o << 1 | 1]);
}
node query(int o, int l, int r, int x, int y) {
  if ((l == x) && (r == y)) {
    return t[o];
  }
  int mid = (l + r) >> 1;
  if (t[o].rev) {
    pushdown(o << 1);
    pushdown(o << 1 | 1);
    t[o].rev ^= 1;
  }
  if (y <= mid)
    return query(o << 1, l, mid, x, y);
  else if (x > mid)
    return query(o << 1 | 1, mid + 1, r, x, y);
  else {
    return merge(query(o << 1, l, mid, x, mid),
                 query(o << 1 | 1, mid + 1, r, mid + 1, y));
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    change(1, 1, n, i, x);
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    scanf("%d", &op);
    if (op == 0) {
      scanf("%d%d", &x, &k);
      change(1, 1, n, x, k);
    } else {
      scanf("%d%d%d", &x, &y, &k);
      int ans = 0;
      while (k--) {
        node tmp = query(1, 1, n, x, y);
        if (tmp.smax.s < 0) break;
        ans += tmp.smax.s;
        rev(1, 1, n, tmp.smax.l, tmp.smax.r);
        q.push(tmp);
      }
      cout << ans << endl;
      while (!q.empty()) {
        node h = q.front();
        q.pop();
        rev(1, 1, n, h.smax.l, h.smax.r);
      }
    }
  }
  return 0;
}
