#include <bits/stdc++.h>
using namespace std;
void setIO(string NAME) {}
inline long long gI() {
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  long long flag = 1, p = 0;
  if (c == '-') flag = -1, c = getchar();
  while (c >= '0' && c <= '9') p = p * 10 + (c - '0'), c = getchar();
  return p * flag;
}
int gs(char *C) {
  char c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  int l = 0;
  while (c != ' ' && c != '\n' && c != EOF) C[l++] = c, c = getchar();
  C[l] = 0;
  return l;
}
template <class T>
void debug(const T a, const int &n) {
  for (int i = 0; i < n; ++i) printf("%d%c", a[i], (i == n - 1) ? '\n' : ' ');
}
const int inf = ~0U >> 1, maxn = 100000 + 10, maxk = 20 + 10;
int n, m;
int a[maxn], L[maxk], R[maxk];
struct node {
  node *l, *r;
  bool rev;
  int markl, markr, mark;
  int sum, Lmax, Rmax, Lmin, Rmin, Mmax, Mmin;
  int Lmaxp, Rmaxp, Lminp, Rminp, Mmaxl, Mmaxr, Mminl, Mminr;
  void upd();
  void revIt();
  void relax();
  node();
} mem[maxn << 1], *C = mem, *root, Tnull, *null = &Tnull;
node::node() { l = r = null; }
void node::revIt() {
  if (this == null) return;
  rev ^= 1;
  sum = -sum;
  if (mark != -1) mark = 1 - mark;
  markl = 1 - markl, markr = 1 - markr;
  swap(Lmax, Lmin), swap(Rmax, Rmin), swap(Mmax, Mmin);
  Lmax = -Lmax, Lmin = -Lmin;
  Rmax = -Rmax, Rmin = -Rmin;
  Mmax = -Mmax, Mmin = -Mmin;
  swap(Lmaxp, Lminp), swap(Rmaxp, Rminp), swap(Mmaxl, Mminl),
      swap(Mmaxr, Mminr);
}
void node::relax() {
  if (rev) {
    l->revIt(), r->revIt();
    rev = 0;
  }
}
void node::upd() {
  if (l->mark != r->mark)
    mark = -1;
  else
    mark = l->mark;
  markl = l->markl, markr = r->markr;
  sum = l->sum + r->sum;
  Lmax = l->Lmax, Lmaxp = l->Lmaxp;
  if (l->mark != -1 && r->markl == l->mark && l->sum + r->Lmax > Lmax)
    Lmax = l->sum + r->Lmax, Lmaxp = r->Lmaxp;
  Lmin = l->Lmin, Lminp = l->Lminp;
  if (l->mark != -1 && r->markl == l->mark && l->sum + r->Lmin < Lmin)
    Lmin = l->sum + r->Lmin, Lminp = r->Lminp;
  Rmax = r->Rmax, Rmaxp = r->Rmaxp;
  if (r->mark != -1 && l->markr == r->mark && r->sum + l->Rmax > Rmax)
    Rmax = r->sum + l->Rmax, Rmaxp = l->Rmaxp;
  Rmin = r->Rmin, Rminp = r->Rminp;
  if (r->mark != -1 && l->markr == r->mark && r->sum + l->Rmin < Rmin)
    Rmin = r->sum + l->Rmin, Rminp = l->Rminp;
  if (l->Mmax > r->Mmax)
    Mmax = l->Mmax, Mmaxl = l->Mmaxl, Mmaxr = l->Mmaxr;
  else
    Mmax = r->Mmax, Mmaxl = r->Mmaxl, Mmaxr = r->Mmaxr;
  if (l->markr == r->markl && l->Rmax + r->Lmax > Mmax)
    Mmax = l->Rmax + r->Lmax, Mmaxl = l->Rmaxp, Mmaxr = r->Lmaxp;
  if (l->Mmin < r->Mmin)
    Mmin = l->Mmin, Mminl = l->Mminl, Mminr = l->Mminr;
  else
    Mmin = r->Mmin, Mminl = r->Mminl, Mminr = r->Mminr;
  if (l->markr == r->markl && l->Rmin + r->Lmin < Mmin)
    Mmin = l->Rmin + r->Lmin, Mminl = l->Rminp, Mminr = r->Lminp;
}
node *mk(int pos, int k, node *x = C) {
  x->markl = x->markr = x->mark = 0, x->rev = 0;
  x->sum = k;
  if (k > 0) {
    x->Mmax = x->Lmax = x->Rmax = k;
    x->Mmaxl = x->Mmaxr = x->Lmaxp = x->Rmaxp = pos;
    x->Mmin = x->Lmin = x->Rmin = 0;
    x->Mminl = x->Lminp = pos - 1;
    x->Mminr = x->Rminp = pos + 1;
  }
  if (k < 0) {
    x->Mmin = x->Lmin = x->Rmin = k;
    x->Mminl = x->Mminr = x->Lminp = x->Rminp = pos;
    x->Mmax = x->Lmax = x->Rmax = 0;
    x->Mmaxl = x->Lmaxp = pos - 1;
    x->Mmaxr = x->Rmaxp = pos + 1;
  }
  if (k == 0) {
    x->Mmax = x->Lmax = x->Rmax = x->Mmin = x->Lmin = x->Rmin = 0;
    x->Mmaxl = x->Mmaxr = x->Mminl = x->Mminr = x->Lmaxp = x->Lminp = x->Rmaxp =
        x->Rminp = pos;
  }
  if (x == C) return C++;
  return x;
}
void modify(node *x, int L, int R, int pos, int k) {
  x->relax();
  if (L == R) {
    x = mk(pos, k, x);
    return;
  }
  int M = L + R >> 1;
  if (pos <= M)
    modify(x->l, L, M, pos, k);
  else
    modify(x->r, M + 1, R, pos, k);
  x->upd();
}
node *build(int L, int R) {
  if (L > R) return null;
  int M = L + R >> 1;
  node *x = mk(M, a[M]);
  if (L == R) return x;
  x->l = build(L, M), x->r = build(M + 1, R);
  x->upd();
  return x;
}
void reverse(node *x, int L, int R, int l, int r) {
  x->relax();
  if (l <= L && R <= r) {
    x->revIt();
    return;
  }
  int M = L + R >> 1;
  if (M < r) reverse(x->r, M + 1, R, l, r);
  if (l <= M) reverse(x->l, L, M, l, r);
  x->upd();
}
node query(node *x, int L, int R, int l, int r) {
  x->relax();
  if (l <= L && R <= r) return *x;
  int M = L + R >> 1;
  if (r <= M) return query(x->l, L, M, l, r);
  if (M < l) return query(x->r, M + 1, R, l, r);
  node LP = query(x->l, L, M, l, r), RP = query(x->r, M + 1, R, l, r), MP;
  MP.l = &LP, MP.r = &RP, MP.upd();
  return MP;
}
int main() {
  setIO("test");
  n = gI();
  for (int i = 1; i <= n; ++i) a[i] = gI();
  root = build(1, n);
  m = gI();
  for (int z = 1; z <= m; ++z) {
    int type = gI();
    if (type == 0) {
      int x = gI(), val = gI();
      modify(root, 1, n, x, val);
    } else {
      int l = gI(), r = gI(), k = gI(), ans = 0;
      for (int i = 0; i < k; ++i) {
        node now = query(root, 1, n, l, r);
        if (now.Mmax <= 0)
          L[i] = R[i] = -1;
        else {
          ans += now.Mmax;
          L[i] = now.Mmaxl, R[i] = now.Mmaxr;
          if (L[i] > R[i]) return 0;
          reverse(root, 1, n, L[i], R[i]);
        }
      }
      printf("%d\n", ans);
      for (int i = 0; i < k; ++i) {
        if (L[i] == -1) break;
        reverse(root, 1, n, L[i], R[i]);
      }
    }
  }
  return 0;
}
