#include <bits/stdc++.h>
using namespace std;
const int MX = 100010;
int N, M;
vector<int> arr;
struct node {
  int opt[22], lopt[22], ropt[22], lropt[22];
  void init() {
    for (int i = 0; i < 22; i++) {
      opt[i] = lopt[i] = ropt[i] = lropt[i] = i ? -1e9 : 0;
    }
  }
};
node mrg(node a, node b) {
  node ret;
  ret.init();
  for (int i = 1; i < 22; i++) {
    for (int j = 0; j <= i; j++) {
      ret.opt[i] = max(ret.opt[i], a.opt[j] + b.opt[i - j]);
    }
    for (int j = 1; j <= i; j++) {
      ret.opt[i] = max(ret.opt[i], a.ropt[j] + b.lopt[i + 1 - j]);
    }
  }
  for (int i = 1; i < 22; i++) {
    for (int j = 1; j <= i; j++) {
      ret.lopt[i] = max(ret.lopt[i], a.lopt[j] + b.opt[i - j]);
      ret.lopt[i] = max(ret.lopt[i], a.lropt[j] + b.lopt[i + 1 - j]);
    }
  }
  for (int i = 1; i < 22; i++) {
    for (int j = 1; j <= i; j++) {
      ret.ropt[i] = max(ret.ropt[i], a.opt[i - j] + b.ropt[j]);
      ret.ropt[i] = max(ret.ropt[i], a.ropt[i + 1 - j] + b.lropt[j]);
    }
  }
  for (int i = 1; i < 22; i++) {
    for (int j = 1; j < i; j++) {
      ret.lropt[i] = max(ret.lropt[i], a.lopt[j] + b.ropt[i - j]);
    }
    for (int j = 1; j <= i; j++) {
      ret.lropt[i] = max(ret.lropt[i], a.lropt[j] + b.lropt[i + 1 - j]);
    }
  }
  return ret;
}
struct BIT {
  node tree[4 * MX];
  void init(int n) { build(0, n - 1, 1); }
  void build(int l, int r, int n) {
    if (l == r) {
      tree[n].init();
      tree[n].opt[1] = tree[n].lopt[1] = tree[n].ropt[1] = tree[n].lropt[1] =
          arr[l];
      return;
    }
    int m = (l + r) >> 1;
    build(l, m, 2 * n);
    build(m + 1, r, 2 * n + 1);
    tree[n] = mrg(tree[2 * n], tree[2 * n + 1]);
  }
  void upd(int idx, int val, int l, int r, int n) {
    if (idx < l || r < idx) return;
    if (l == r) {
      tree[n].init();
      tree[n].opt[1] = tree[n].lopt[1] = tree[n].ropt[1] = tree[n].lropt[1] =
          val;
      return;
    }
    int m = (l + r) >> 1;
    upd(idx, val, l, m, 2 * n);
    upd(idx, val, m + 1, r, 2 * n + 1);
    tree[n] = mrg(tree[2 * n], tree[2 * n + 1]);
  }
  node quer(int a, int b, int l, int r, int n) {
    if (b < l || r < a) {
      node ret;
      ret.init();
      return ret;
    }
    if (a <= l && r <= b) return tree[n];
    int m = (l + r) >> 1;
    node L = quer(a, b, l, m, 2 * n);
    node R = quer(a, b, m + 1, r, 2 * n + 1);
    return mrg(L, R);
  }
} bit;
int main() {
  scanf("%d", &N);
  arr.resize(N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &arr[i]);
  }
  bit.init(N);
  scanf("%d", &M);
  for (int i = 0; i < M; i++) {
    int t;
    scanf("%d", &t);
    if (t == 0) {
      int idx, val;
      scanf("%d %d", &idx, &val);
      idx--;
      bit.upd(idx, val, 0, N - 1, 1);
    } else {
      int l, r, k;
      scanf("%d %d %d", &l, &r, &k);
      l--;
      r--;
      node t = bit.quer(l, r, 0, N - 1, 1);
      int mx = -1e9;
      for (int j = 0; j <= k; j++) mx = max(mx, t.opt[j]);
      printf("%d\n", mx);
    }
  }
}
