#include <bits/stdc++.h>
using namespace std;
int rd() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return f * x;
}
int n, k;
pair<int, int> fx[100005];
int cnt;
int a[100005];
struct node {
  int sum, mxs, lmx, rmx;
  int l, r, rr, ll;
} tree[2][100005 << 2];
bool tag[100005 << 2];
node Merge(node x, node y) {
  node t;
  t.sum = x.sum + y.sum;
  t.mxs = t.lmx = t.rmx = -0x3f3f3f3f;
  if (x.lmx > t.lmx) t.lmx = x.lmx, t.rr = x.rr;
  if (x.sum + y.lmx > t.lmx) t.lmx = x.sum + y.lmx, t.rr = y.rr;
  if (y.rmx > t.rmx) t.rmx = y.rmx, t.ll = y.ll;
  if (y.sum + x.rmx > t.rmx) t.rmx = y.sum + x.rmx, t.ll = x.ll;
  if (x.mxs > t.mxs) t.mxs = x.mxs, t.l = x.l, t.r = x.r;
  if (y.mxs > t.mxs) t.mxs = y.mxs, t.l = y.l, t.r = y.r;
  if (x.rmx + y.lmx > t.mxs) t.mxs = x.rmx + y.lmx, t.l = x.ll, t.r = y.rr;
  return t;
}
void PushUp(int i) {
  tree[0][i] = Merge(tree[0][i << 1], tree[0][i << 1 | 1]);
  tree[1][i] = Merge(tree[1][i << 1], tree[1][i << 1 | 1]);
}
void Init(int i, int l, int val) {
  tree[0][i].sum = tree[0][i].mxs = tree[0][i].lmx = tree[0][i].rmx = val;
  tree[1][i].sum = tree[1][i].mxs = tree[1][i].lmx = tree[1][i].rmx = -val;
  tree[0][i].l = tree[0][i].r = tree[0][i].rr = tree[0][i].ll = l;
  tree[1][i].l = tree[1][i].r = tree[1][i].rr = tree[1][i].ll = l;
}
void Build(int i, int l, int r) {
  if (l == r) {
    Init(i, l, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  Build(i << 1, l, mid);
  Build(i << 1 | 1, mid + 1, r);
  PushUp(i);
}
void Shift(int i) {
  swap(tree[0][i], tree[1][i]);
  tag[i] ^= 1;
}
void PushDown(int i) {
  if (tag[i] == 1) {
    Shift(i << 1);
    Shift(i << 1 | 1);
    tag[i] = 0;
  }
}
void Update(int i, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    Shift(i);
    return;
  }
  PushDown(i);
  int mid = (l + r) >> 1;
  if (ql <= mid) Update(i << 1, l, mid, ql, qr);
  if (qr > mid) Update(i << 1 | 1, mid + 1, r, ql, qr);
  PushUp(i);
}
node Query(int i, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return tree[0][i];
  PushDown(i);
  int mid = (l + r) >> 1;
  if (qr <= mid)
    return Query(i << 1, l, mid, ql, qr);
  else if (ql > mid)
    return Query(i << 1 | 1, mid + 1, r, ql, qr);
  return Merge(Query(i << 1, l, mid, ql, qr),
               Query(i << 1 | 1, mid + 1, r, ql, qr));
}
void Modify(int i, int l, int r, int pos, int val) {
  if (l == r) {
    Init(i, l, val);
    return;
  }
  PushDown(i);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    Modify(i << 1, l, mid, pos, val);
  else
    Modify(i << 1 | 1, mid + 1, r, pos, val);
  PushUp(i);
}
int main() {
  n = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();
  Build(1, 1, n);
  int Q = rd();
  while (Q--) {
    int opt = rd();
    if (opt == 0) {
      int i = rd(), val = rd();
      Modify(1, 1, n, i, val);
    } else {
      int l = rd(), r = rd(), k = rd();
      int res = 0;
      while (k--) {
        node ans = Query(1, 1, n, l, r);
        if (ans.mxs <= 0) break;
        res += ans.mxs;
        fx[++cnt] = make_pair(ans.l, ans.r);
        Update(1, 1, n, ans.l, ans.r);
      }
      printf("%d\n", res);
      for (int i = cnt; i >= 1; i--) Update(1, 1, n, fx[i].first, fx[i].second);
      cnt = 0;
    }
  }
  return 0;
}
