#include <bits/stdc++.h>
using namespace std;
int Q, P, V, L, R, K;
const int n = 1 << 18;
int A[n];
struct Query {
  pair<int, pair<int, int> > lma, rma, lmi, rmi, sum, ma, mi;
};
pair<int, pair<int, int> > con(pair<int, pair<int, int> > p1,
                               pair<int, pair<int, int> > p2) {
  return make_pair(p1.first + p2.first,
                   make_pair(p1.second.first, p2.second.second));
}
Query unite(Query q1, Query q2) {
  if (q1.sum.first == (1 << 30)) return q2;
  if (q2.sum.first == (1 << 30)) return q1;
  Query res;
  res.lma = max(q1.lma, con(q1.sum, q2.lma));
  res.rma = max(q2.rma, con(q1.rma, q2.sum));
  res.lmi = min(q1.lmi, con(q1.sum, q2.lmi));
  res.rmi = min(q2.rmi, con(q1.rmi, q2.sum));
  res.ma = max(max(q1.ma, q2.ma), con(q1.rma, q2.lma));
  res.mi = min(min(q1.mi, q2.mi), con(q1.rmi, q2.lmi));
  res.sum = con(q1.sum, q2.sum);
  return res;
}
Query invq(Query q) {
  Query res;
  res.lmi = q.lma, res.rmi = q.rma, res.lma = q.lmi, res.rma = q.rmi,
  res.sum = q.sum, res.ma = q.mi, res.mi = q.ma;
  res.lmi.first *= -1, res.rmi.first *= -1, res.lma.first *= -1,
      res.rma.first *= -1, res.sum.first *= -1, res.ma.first *= -1,
      res.mi.first *= -1;
  return res;
}
bool invf[n * 2 - 1];
Query dat[n * 2 - 1];
void seg_update(int i, int v) {
  vector<int> ls;
  int tmp = i;
  while (tmp) tmp = (tmp - 1) / 2, ls.push_back(tmp);
  for (int ai = ls.size() - 1; ai >= 0; ai--) {
    int k = ls[ai];
    if (invf[k]) {
      invf[k] = false;
      ;
      invf[k * 2 + 1] = !invf[k * 2 + 1];
      invf[k * 2 + 2] = !invf[k * 2 + 2];
      dat[k * 2 + 1] = invq(dat[k * 2 + 1]);
      dat[k * 2 + 2] = invq(dat[k * 2 + 2]);
    }
  }
  A[i] = v;
  if (A[i] >= 0) {
    dat[i + n - 1].lma = make_pair(A[i], make_pair(i, i + 1));
    dat[i + n - 1].rma = make_pair(A[i], make_pair(i, i + 1));
    dat[i + n - 1].ma = make_pair(A[i], make_pair(i, i + 1));
    dat[i + n - 1].lmi = make_pair(0, make_pair(i, i));
    dat[i + n - 1].rmi = make_pair(0, make_pair(i + 1, i + 1));
    dat[i + n - 1].mi = make_pair(0, make_pair(i, i));
  } else {
    dat[i + n - 1].lmi = make_pair(A[i], make_pair(i, i + 1));
    dat[i + n - 1].rmi = make_pair(A[i], make_pair(i, i + 1));
    dat[i + n - 1].mi = make_pair(A[i], make_pair(i, i + 1));
    dat[i + n - 1].lma = make_pair(0, make_pair(i, i));
    dat[i + n - 1].rma = make_pair(0, make_pair(i + 1, i + 1));
    dat[i + n - 1].ma = make_pair(0, make_pair(i, i));
  }
  dat[i + n - 1].sum = make_pair(A[i], make_pair(i, i + 1));
  invf[i + n - 1] = false;
  i += n - 1;
  while (i) {
    i = (i - 1) / 2;
    dat[i] = unite(dat[i * 2 + 1], dat[i * 2 + 2]);
  }
}
void inv(int a, int b, int k, int l, int r) {
  if (r <= a || b <= l) return;
  if (a <= l && r <= b) {
    invf[k] = !invf[k];
    dat[k] = invq(dat[k]);
    return;
  }
  if (invf[k]) {
    invf[k] = false;
    dat[k * 2 + 1] = invq(dat[k * 2 + 1]);
    dat[k * 2 + 2] = invq(dat[k * 2 + 2]);
    invf[k * 2 + 1] = !invf[k * 2 + 1];
    invf[k * 2 + 2] = !invf[k * 2 + 2];
  }
  inv(a, b, k * 2 + 1, l, (l + r) / 2);
  inv(a, b, k * 2 + 2, (l + r) / 2, r);
  dat[k] = unite(dat[k * 2 + 1], dat[k * 2 + 2]);
}
Query calc(int a, int b, int k, int l, int r) {
  if (r <= a || b <= l) {
    Query res;
    res.sum.first = (1 << 30);
    return res;
  }
  if (a <= l && r <= b) return dat[k];
  if (invf[k]) {
    invf[k] = false;
    dat[k * 2 + 1] = invq(dat[k * 2 + 1]);
    dat[k * 2 + 2] = invq(dat[k * 2 + 2]);
    invf[k * 2 + 1] = !invf[k * 2 + 1];
    invf[k * 2 + 2] = !invf[k * 2 + 2];
  }
  return unite(calc(a, b, k * 2 + 1, l, (l + r) / 2),
               calc(a, b, k * 2 + 2, (l + r) / 2, r));
}
int main() {
  scanf("%d", &Q);
  for (int(i) = 0; (i) < (Q); (i)++) scanf("%d", &A[i]);
  scanf("%d", &Q);
  for (int(i) = 0; (i) < (n); (i)++) {
    if (A[i] >= 0) {
      dat[i + n - 1].lma = make_pair(A[i], make_pair(i, i + 1));
      dat[i + n - 1].rma = make_pair(A[i], make_pair(i, i + 1));
      dat[i + n - 1].ma = make_pair(A[i], make_pair(i, i + 1));
      dat[i + n - 1].lmi = make_pair(0, make_pair(i, i));
      dat[i + n - 1].rmi = make_pair(0, make_pair(i + 1, i + 1));
      dat[i + n - 1].mi = make_pair(0, make_pair(i, i));
    } else {
      dat[i + n - 1].lmi = make_pair(A[i], make_pair(i, i + 1));
      dat[i + n - 1].rmi = make_pair(A[i], make_pair(i, i + 1));
      dat[i + n - 1].mi = make_pair(A[i], make_pair(i, i + 1));
      dat[i + n - 1].lma = make_pair(0, make_pair(i, i));
      dat[i + n - 1].rma = make_pair(0, make_pair(i + 1, i + 1));
      dat[i + n - 1].ma = make_pair(0, make_pair(i, i));
    }
    dat[i + n - 1].sum = make_pair(A[i], make_pair(i, i + 1));
  }
  for (int i = n - 2; i >= 0; i--)
    dat[i] = unite(dat[i * 2 + 1], dat[i * 2 + 2]);
  while (Q--) {
    scanf("%d", &V);
    if (V == 0) {
      scanf("%d%d", &P, &V);
      P--;
      seg_update(P, V);
    } else {
      scanf("%d%d%d", &L, &R, &K), L--;
      Query res = calc(L, R, 0, 0, n);
      int ans = res.ma.first;
      vector<pair<int, int> > iv;
      int tt = ans;
      for (int(i) = 0; (i) < (K - 1); (i)++) {
        if (res.ma.first == 0) break;
        iv.push_back(res.ma.second);
        inv(res.ma.second.first, res.ma.second.second, 0, 0, n);
        res = calc(L, R, 0, 0, n);
        ans = max(ans, tt + res.ma.first);
        tt += res.ma.first;
      }
      for (int(i) = 0; (i) < (iv.size()); (i)++)
        inv(iv[i].first, iv[i].second, 0, 0, n);
      printf("%d\n", ans);
    }
  }
}
