#include <bits/stdc++.h>
const int N = 400000 + 9;
int key[N], n, p[N], l[N], r[N], sz[N], rt, m, _L, _R;
bool nag[N];
struct Segment {
  int l, r, val;
  Segment() : l(0), r(0), val(0) {}
  Segment(const int _l, const int _r, const int _val)
      : l(_l), r(_r), val(_val) {}
  Segment operator+(const Segment &o) const {
    if (!l && !o.l) return Segment();
    if (!l) return o;
    if (!o.l) return *this;
    return Segment(l, o.r, val + o.val);
  }
} c[30], sum[N], maxL[N], minL[N], maxR[N], minR[N], maxS[N], minS[N];
inline Segment max(const Segment &x, const Segment &y) {
  return x.val < y.val ? y : x;
}
inline Segment min(const Segment &x, const Segment &y) {
  return x.val < y.val ? x : y;
}
inline void iswap(Segment &x, Segment &y) {
  x.val = -x.val;
  y.val = -y.val;
  Segment t = x;
  x = y;
  y = t;
}
inline void rls(int x) {
  if (!x) return;
  if (nag[x]) {
    nag[x] = false;
    nag[l[x]] ^= 1;
    nag[r[x]] ^= 1;
    sum[x].val *= -1;
    iswap(minL[x], maxL[x]);
    iswap(minR[x], maxR[x]);
    iswap(minS[x], maxS[x]);
  }
}
inline void update1(int x) {
  if (!x) return;
  sum[x] = sum[l[x]] + sum[r[x]];
  maxS[x] = max(max(maxS[l[x]], maxS[r[x]]), maxR[l[x]] + maxL[r[x]]);
  maxL[x] = max(maxL[l[x]], sum[l[x]] + maxL[r[x]]);
  maxR[x] = max(maxR[r[x]], maxR[l[x]] + sum[r[x]]);
}
inline void update(int x) {
  if (!x) return;
  rls(l[x]);
  rls(r[x]);
  sum[x] = sum[l[x]] + sum[r[x]];
  maxS[x] = max(max(maxS[l[x]], maxS[r[x]]), maxR[l[x]] + maxL[r[x]]);
  minS[x] = min(min(minS[l[x]], minS[r[x]]), minR[l[x]] + minL[r[x]]);
  maxL[x] = max(maxL[l[x]], sum[l[x]] + maxL[r[x]]);
  minL[x] = min(minL[l[x]], sum[l[x]] + minL[r[x]]);
  maxR[x] = max(maxR[r[x]], maxR[l[x]] + sum[r[x]]);
  minR[x] = min(minR[r[x]], minR[l[x]] + sum[r[x]]);
}
inline void initnode(int x, int p) {
  sum[x] = Segment(p, p, key[p]);
  minS[x] = maxS[x] = sum[x];
  minL[x] = maxL[x] = sum[x];
  minR[x] = maxR[x] = sum[x];
}
void build(int id, int L, int R) {
  if (L == R) return (void)(initnode(id, L));
  l[id] = id * 2;
  r[id] = id * 2 + 1;
  const int mid = (L + R) / 2;
  build(id * 2, L, mid);
  build(id * 2 + 1, mid + 1, R);
  update(id);
}
void _nag(int id, int l, int r) {
  if (_L <= l && r <= _R) {
    nag[id] ^= 1;
    rls(id);
    return;
  }
  if (nag[id]) rls(id);
  const int mid = (l + r) / 2;
  if (_L <= mid) _nag(id * 2, l, mid);
  if (mid < _R) _nag(id * 2 + 1, mid + 1, r);
  update(id);
}
void nagetive(int l, int r) {
  _L = l;
  _R = r;
  _nag(1, 1, n);
}
void modify(int id, int l, int r, int p) {
  if (nag[id]) rls(id);
  if (l == r) return (void)(initnode(id, l));
  const int mid = (l + r) / 2;
  if (p <= mid)
    modify(id * 2, l, mid, p);
  else
    modify(id * 2 + 1, mid + 1, r, p);
  update(id);
}
void read(int &x) {
  char c = getchar(), p = 0;
  for (; c < '0' || c > '9'; c = getchar()) p = c;
  x = 0;
  for (; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + c - '0';
  if (p == '-') x *= -1;
}
void copy(int x, int id) {
  maxS[x] = maxS[id];
  maxL[x] = maxL[id];
  maxR[x] = maxR[id];
  sum[x] = sum[id];
}
void _query(int id, int L, int R) {
  if (nag[id]) rls(id);
  if (_L <= L && R <= _R) {
    if (_L == L)
      copy(N - 1, id);
    else {
      copy(N - 2, N - 1);
      l[N - 1] = N - 2;
      r[N - 1] = id;
      update1(N - 1);
    }
    return;
  }
  const int mid = (L + R) / 2;
  if (_L <= mid) _query(id * 2, L, mid);
  if (mid < _R) _query(id * 2 + 1, mid + 1, R);
}
Segment query(int L, int R) {
  _L = L;
  _R = R;
  _query(1, 1, n);
  return maxS[N - 1];
}
void print(int id, int l, int r) {
  if (nag[id]) rls(id);
  if (l == r) {
    printf("%d ", sum[id].val);
    return;
  }
  const int mid = (l + r) / 2;
  print(id * 2, l, mid);
  print(id * 2 + 1, mid + 1, r);
}
int main() {
  read(n);
  for (int i = 1; i <= n; ++i) read(key[i]);
  build(1, 1, n);
  read(m);
  for (int I = 1; I <= m; ++I) {
    int opt, pos, k, val, L, R;
    read(opt);
    if (opt == 0) {
      read(pos);
      read(val);
      key[pos] = val;
      modify(1, 1, n, pos);
    } else {
      read(L);
      read(R);
      read(k);
      int tot = 0, res = 0;
      for (int i = 0; i < k; ++i) {
        Segment cnt = query(L, R);
        if (cnt.l && cnt.val > 0) {
          res += cnt.val;
          c[tot++] = cnt;
          nagetive(cnt.l, cnt.r);
        } else
          break;
      }
      for (int i = 0; i < tot; ++i) nagetive(c[i].l, c[i].r);
      printf("%d\n", res);
    }
  }
}
