#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct D {
  int a[21];
};
struct Segment_tree {
  int left, right;
  D dp, dpl, dpr, dplr;
} Segtree[MAXN * 3];
int n;
int a[MAXN];
struct C {
  D c[4];
};
inline void push_up(int p) {
  for (int i = 0; i <= 20; i++)
    Segtree[p].dp.a[i] = Segtree[p].dpl.a[i] = Segtree[p].dpr.a[i] =
        Segtree[p].dplr.a[i] = -1000000000;
  for (int i = 0; i <= 20; i++)
    for (int j = 0; j <= 20 - i; j++) {
      Segtree[p].dp.a[i + j] =
          max(Segtree[p].dp.a[i + j],
              Segtree[2 * p].dp.a[i] + Segtree[2 * p + 1].dp.a[j]);
      if (i)
        Segtree[p].dpl.a[i + j] =
            max(Segtree[p].dpl.a[i + j],
                Segtree[2 * p].dpl.a[i] + Segtree[2 * p + 1].dp.a[j]);
      if (j)
        Segtree[p].dpr.a[i + j] =
            max(Segtree[p].dpr.a[i + j],
                Segtree[2 * p].dp.a[i] + Segtree[2 * p + 1].dpr.a[j]);
      if (i && j)
        Segtree[p].dplr.a[i + j] =
            max(Segtree[p].dplr.a[i + j],
                Segtree[2 * p].dpl.a[i] + Segtree[2 * p + 1].dpr.a[j]);
    }
  for (int i = 1; i <= 20; i++)
    for (int j = 1; j <= 21 - i; j++) {
      Segtree[p].dp.a[i + j - 1] =
          max(Segtree[p].dp.a[i + j - 1],
              Segtree[2 * p].dpr.a[i] + Segtree[2 * p + 1].dpl.a[j]);
      Segtree[p].dpl.a[i + j - 1] =
          max(Segtree[p].dpl.a[i + j - 1],
              Segtree[2 * p].dplr.a[i] + Segtree[2 * p + 1].dpl.a[j]);
      Segtree[p].dpr.a[i + j - 1] =
          max(Segtree[p].dpr.a[i + j - 1],
              Segtree[2 * p].dpr.a[i] + Segtree[2 * p + 1].dplr.a[j]);
      Segtree[p].dplr.a[i + j - 1] =
          max(Segtree[p].dplr.a[i + j - 1],
              Segtree[2 * p].dplr.a[i] + Segtree[2 * p + 1].dplr.a[j]);
    }
}
void Build(int p, int l, int r) {
  Segtree[p].left = l;
  Segtree[p].right = r;
  if (l == r) {
    for (int i = 1; i <= 20; i++)
      Segtree[p].dp.a[i] = max(0, a[l]),
      Segtree[p].dpl.a[i] = Segtree[p].dpr.a[i] = Segtree[p].dplr.a[i] = a[l];
  } else {
    int mid = (l + r) >> 1;
    Build(2 * p, l, mid);
    Build(2 * p + 1, mid + 1, r);
    push_up(p);
  }
}
void Change(int p, int l, int v) {
  if (Segtree[p].left == l && Segtree[p].right == l) {
    for (int i = 1; i <= 20; i++)
      Segtree[p].dp.a[i] = max(0, v),
      Segtree[p].dpl.a[i] = Segtree[p].dpr.a[i] = Segtree[p].dplr.a[i] = v;
  } else {
    int mid = (Segtree[p].left + Segtree[p].right) >> 1;
    if (l <= mid)
      Change(2 * p, l, v);
    else
      Change(2 * p + 1, l, v);
    push_up(p);
  }
}
inline C cmb(const C &x, const C &y, int k) {
  C ans;
  for (int i = 0; i <= k; i++)
    ans.c[0].a[i] = ans.c[1].a[i] = ans.c[2].a[i] = ans.c[3].a[i] = -1000000000;
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= k - i; j++) {
      ans.c[0].a[i + j] = max(ans.c[0].a[i + j], x.c[0].a[i] + y.c[0].a[j]);
      if (i)
        ans.c[1].a[i + j] = max(ans.c[1].a[i + j], x.c[1].a[i] + y.c[0].a[j]);
      if (j)
        ans.c[2].a[i + j] = max(ans.c[2].a[i + j], x.c[0].a[i] + y.c[2].a[j]);
      if (i && j)
        ans.c[3].a[i + j] = max(ans.c[3].a[i + j], x.c[1].a[i] + y.c[2].a[j]);
    }
  for (int i = 1; i <= k; i++)
    for (int j = 1; j <= k + 1 - i; j++) {
      ans.c[0].a[i + j - 1] =
          max(ans.c[0].a[i + j - 1], x.c[2].a[i] + y.c[1].a[j]);
      ans.c[1].a[i + j - 1] =
          max(ans.c[1].a[i + j - 1], x.c[3].a[i] + y.c[1].a[j]);
      ans.c[2].a[i + j - 1] =
          max(ans.c[2].a[i + j - 1], x.c[2].a[i] + y.c[3].a[j]);
      ans.c[3].a[i + j - 1] =
          max(ans.c[3].a[i + j - 1], x.c[3].a[i] + y.c[3].a[j]);
    }
  return ans;
}
C Query(int p, int l, int r, int k) {
  if (Segtree[p].left == l && Segtree[p].right == r) {
    C tmp;
    tmp.c[0] = Segtree[p].dp;
    tmp.c[1] = Segtree[p].dpl;
    tmp.c[2] = Segtree[p].dpr;
    tmp.c[3] = Segtree[p].dplr;
    return tmp;
  } else {
    int mid = (Segtree[p].left + Segtree[p].right) >> 1;
    if (r <= mid)
      return Query(2 * p, l, r, k);
    else if (l > mid)
      return Query(2 * p + 1, l, r, k);
    else {
      C x = Query(2 * p, l, mid, k), y = Query(2 * p + 1, mid + 1, r, k);
      return cmb(x, y, k);
    }
  }
}
int getint() {
  char ch = getchar();
  for (; (ch > '9' || ch < '0') && ch != '-'; ch = getchar())
    ;
  bool f = 0;
  if (ch == '-') f = 1, ch = getchar();
  int tmp = 0;
  for (; '0' <= ch && ch <= '9'; ch = getchar()) tmp = tmp * 10 + int(ch) - 48;
  if (f) tmp = -tmp;
  return tmp;
}
int main() {
  n = getint();
  for (int i = 1; i <= n; i++) a[i] = getint();
  Build(1, 1, n);
  int T;
  scanf("%d", &T);
  while (T--) {
    int q, l, r, k;
    q = getint();
    l = getint();
    r = getint();
    if (q == 0)
      Change(1, l, r);
    else {
      k = getint();
      printf("%d\n", Query(1, l, r, k).c[0].a[k]);
    }
  }
  return 0;
}
