#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, K = 20;
int a[N], n;
struct node {
  int f[K + 1][2][2], lv, rv, left, right;
  node() : left(-1), right(-1) { assign(); }
  inline const int len() { return rv - lv + 1; }
  void assign(int newVal = -1e9) {
    for (int i = 0; i <= K; i++)
      for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++) {
          if (i == 0)
            f[i][x][y] = 0;
          else if (i == 1)
            f[i][x][y] = newVal;
          else
            f[i][x][y] = -1e9;
        }
  }
  void recalc(node &a, node &b) {
    lv = a.lv;
    rv = b.rv;
    assign();
    for (int i = 1; i <= K; i++) {
      if (i + i <= a.len() + 1) {
        if (f[i][0][0] < a.f[i][0][0]) f[i][0][0] = a.f[i][0][0];
        ;
        if (f[i][1][0] < a.f[i][1][0]) f[i][1][0] = a.f[i][1][0];
        ;
      }
      if (i + i <= b.len() + 1) {
        if (f[i][0][0] < b.f[i][0][0]) f[i][0][0] = b.f[i][0][0];
        ;
        if (f[i][0][1] < b.f[i][0][1]) f[i][0][1] = b.f[i][0][1];
        ;
      }
    }
    for (int i = 1; i <= K && i + i <= a.len() + 1; i++)
      for (int j = 1; j <= K && i + j <= K + 1 && j + j <= b.len() + 1; j++) {
        if (f[i + j - 1][0][0] < a.f[i][0][1] + b.f[j][1][0])
          f[i + j - 1][0][0] = a.f[i][0][1] + b.f[j][1][0];
        ;
        if (f[i + j - 1][0][1] < a.f[i][0][1] + b.f[j][1][1])
          f[i + j - 1][0][1] = a.f[i][0][1] + b.f[j][1][1];
        ;
        if (f[i + j - 1][1][0] < a.f[i][1][1] + b.f[j][1][0])
          f[i + j - 1][1][0] = a.f[i][1][1] + b.f[j][1][0];
        ;
        if (f[i + j - 1][1][1] < a.f[i][1][1] + b.f[j][1][1])
          f[i + j - 1][1][1] = a.f[i][1][1] + b.f[j][1][1];
        ;
        if (i + j == K + 1) {
          continue;
        }
        if (f[i + j][0][0] < a.f[i][0][0] + b.f[j][0][0])
          f[i + j][0][0] = a.f[i][0][0] + b.f[j][0][0];
        ;
        if (f[i + j][0][1] < a.f[i][0][0] + b.f[j][0][1])
          f[i + j][0][1] = a.f[i][0][0] + b.f[j][0][1];
        ;
        if (f[i + j][1][0] < a.f[i][1][0] + b.f[j][0][0])
          f[i + j][1][0] = a.f[i][1][0] + b.f[j][0][0];
        ;
        if (f[i + j][1][1] < a.f[i][1][0] + b.f[j][0][1])
          f[i + j][1][1] = a.f[i][1][0] + b.f[j][0][1];
        ;
      }
    for (int i = 0; i <= K && i + i <= len() + 1; i++) {
      if (f[i][1][0] < f[i][1][1]) f[i][1][0] = f[i][1][1];
      ;
      if (f[i][0][1] < f[i][1][1]) f[i][0][1] = f[i][1][1];
      ;
      if (f[i][0][0] < f[i][0][1]) f[i][0][0] = f[i][0][1];
      ;
      if (f[i][0][0] < f[i][1][0]) f[i][0][0] = f[i][1][0];
      ;
    }
  }
} t[N * 2];
void build(int v, int lv, int rv) {
  static int timer = 1;
  t[v].lv = lv;
  t[v].rv = rv;
  if (lv == rv) {
    t[v].assign(a[lv]);
    return;
  }
  t[v].left = timer++;
  t[v].right = timer++;
  int m = (lv + rv) >> 1;
  build(t[v].left, lv, m);
  build(t[v].right, m + 1, rv);
  t[v].recalc(t[t[v].left], t[t[v].right]);
}
void modify(int v, int p, int newVal) {
  if (t[v].lv == p && t[v].rv == p) {
    t[v].assign(newVal);
    return;
  }
  if (p <= t[t[v].left].rv) {
    modify(t[v].left, p, newVal);
  } else {
    modify(t[v].right, p, newVal);
  }
  t[v].recalc(t[t[v].left], t[t[v].right]);
}
node get(int v, int l, int r) {
  if (l <= t[v].lv && t[v].rv <= r) {
    return t[v];
  }
  if (r <= t[t[v].left].rv) {
    return get(t[v].left, l, r);
  }
  if (l >= t[t[v].right].lv) {
    return get(t[v].right, l, r);
  }
  node res, t1, t2;
  t1 = get(t[v].left, l, r);
  t2 = get(t[v].right, l, r);
  res.recalc(t1, t2);
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  build(0, 0, n - 1);
  int m;
  cin >> m;
  while (m--) {
    int action;
    cin >> action;
    if (action == 1) {
      int l, r, k, ans = 0;
      cin >> l >> r >> k;
      l--;
      r--;
      node v = get(0, l, r);
      for (int i = 1; i <= k && i + i <= v.len() + 1; i++) {
        if (ans < v.f[i][0][0]) ans = v.f[i][0][0];
        ;
      }
      cout << ans << "\n";
    } else {
      int p, newVal;
      cin >> p >> newVal;
      p--;
      modify(0, p, newVal);
    }
  }
  return 0;
}
