#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int mod = 1e9 + 7;
inline int sign(double x) { return (x > eps) - (x < -eps); }
inline int add(int a, int b) {
  a += b;
  return a < 0 ? a + mod : a >= mod ? a - mod : a;
}
inline int mul(long long a, long long b) { return a * b % mod; }
const int maxn = 1e5 + 10, INF = 0x3f3f3f3f;
inline void Max(int& a, int b) { a = a < b ? b : a; }
struct node {
  int f[4][22], sum;
  void set(int x) {
    f[0][0] = 0;
    f[1][0] = f[2][0] = f[3][0] = -INF;
    sum = x;
    for (int i = 1; i <= 21; ++i)
      f[0][i] = max(0, x), f[1][i] = f[2][i] = f[3][i] = x;
  }
  node operator+(const node& t) {
    node res;
    res.set(-INF);
    res.sum = sum + t.sum;
    for (int i = 0; i <= 20; ++i) {
      for (int j = 0; i + j <= 21; ++j) {
        if (i + j > 1) {
          Max(res.f[0][i + j - 1], f[2][i] + t.f[1][j]);
          Max(res.f[1][i + j - 1], f[3][i] + t.f[1][j]);
          Max(res.f[2][i + j - 1], f[2][i] + t.f[3][j]);
          Max(res.f[3][i + j - 1], f[3][i] + t.f[3][j]);
        }
        Max(res.f[0][i + j], f[0][i] + t.f[0][j]);
        Max(res.f[1][i + j], f[1][i] + t.f[0][j]);
        Max(res.f[2][i + j], f[0][i] + t.f[2][j]);
        Max(res.f[3][i + j], f[1][i] + t.f[2][j]);
      }
    }
    return res;
  }
} tr[maxn << 2];
void build(int l, int r, int rt) {
  if (l == r) {
    int x;
    scanf("%d", &x);
    tr[rt].set(x);
    return;
  }
  int m = l + r >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
void upd(int p, int x, int l, int r, int rt) {
  if (l == r) {
    tr[rt].set(x);
    return;
  }
  int m = l + r >> 1;
  if (p <= m)
    upd(p, x, l, m, rt << 1);
  else
    upd(p, x, m + 1, r, rt << 1 | 1);
  tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
node qry(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) return tr[rt];
  int m = l + r >> 1;
  if (L <= m && R > m)
    return qry(L, R, l, m, rt << 1) + qry(L, R, m + 1, r, rt << 1 | 1);
  if (L <= m) return qry(L, R, l, m, rt << 1);
  return qry(L, R, m + 1, r, rt << 1 | 1);
}
int main() {
  int n;
  cin >> n;
  build(1, n, 1);
  int m;
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (!op)
      upd(x, y, 1, n, 1);
    else {
      int k;
      scanf("%d", &k);
      node res = qry(x, y, 1, n, 1);
      printf("%d\n", res.f[0][k]);
    }
  }
  return 0;
}
