#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
const int oo = -1e9;
const int maxk = 20;
typedef struct node {
  int dp[maxk + 1][2][2];
  node *lch, *rch;
  node() : dp(), lch(0), rch(0) {}
} * pnode;
int hhh[maxn];
int f[maxk + 1][2][2];
void getf(pnode l, pnode r, bool dir1, bool dir2) {
  int ls = 0, rs = 0;
  bool asd = 0;
  for (int i = 1; i <= maxk; i++) {
    int add = 0, w;
    if (l->dp[ls + 1][dir1][asd] - l->dp[ls][dir1][asd] >
        r->dp[rs + 1][asd][dir2] - r->dp[rs][asd][dir2]) {
      w = 1;
      add = l->dp[ls + 1][dir1][asd] - l->dp[ls][dir1][asd];
    } else {
      w = 2;
      add = r->dp[rs + 1][asd][dir2] - r->dp[rs][asd][dir2];
    }
    if (!asd &&
        l->dp[ls + 1][dir1][1] + r->dp[rs + 1][1][dir2] - f[i - 1][dir1][dir2] >
            add) {
      add = l->dp[ls + 1][dir1][1] + r->dp[rs + 1][1][dir2] -
            f[i - 1][dir1][dir2];
      w = 3;
    } else if (asd &&
               l->dp[ls][dir1][0] + r->dp[rs][0][dir2] - f[i - 1][dir1][dir2] >
                   add) {
      add = l->dp[ls][dir1][0] + r->dp[rs][0][dir2] - f[i - 1][dir1][dir2];
      w = 3;
    }
    f[i][dir1][dir2] = f[i - 1][dir1][dir2] + add;
    if (w == 1) ls++;
    if (w == 2) rs++;
    if (w == 3) {
      if (!asd) {
        ls++;
        rs++;
      }
      asd ^= 1;
    }
    if (i == 1) {
      if (dir1 != 0 || dir2 != 0) {
        ls = rs = 0;
        asd = 0;
      }
      if (dir1 == 1 && dir2 == 0) {
        ls = 1;
        f[1][1][0] = l->dp[1][1][0];
        if (l->dp[1][1][0] < l->dp[1][1][1] + r->dp[1][1][0]) {
          asd = 1;
          rs = 1;
          f[1][1][0] = l->dp[1][1][1] + r->dp[1][1][0];
        }
      }
      if (dir1 == 0 && dir2 == 1) {
        rs = 1;
        f[1][0][1] = r->dp[1][0][1];
        if (r->dp[1][0][1] < l->dp[1][0][1] + r->dp[1][1][1]) {
          asd = 1;
          ls = 1;
          f[1][0][1] = l->dp[1][0][1] + r->dp[1][1][1];
        }
      }
      if (dir1 == 1 && dir2 == 1) {
        asd = 1;
        ls = rs = 1;
        f[1][1][1] = l->dp[1][1][1] + r->dp[1][1][1];
      }
    }
  }
}
pnode root = 0;
void update(pnode r, pnode lch, pnode rch) {
  getf(lch, rch, 0, 0);
  getf(lch, rch, 0, 1);
  getf(lch, rch, 1, 0);
  getf(lch, rch, 1, 1);
  for (int i = 1; i <= maxk; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++) r->dp[i][j][k] = f[i][j][k];
}
void out1(pnode r) {
  for (int i = 1; i <= maxk; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        cout << i << " " << j << " " << k << " " << r->dp[i][j][k] << endl;
}
void out(pnode r, int st, int ed) {
  cout << st << " " << ed << " : " << endl;
  out1(r);
  if (st == ed) return;
  int mid = (st + ed) >> 1;
  out(r->lch, st, mid);
  out(r->rch, mid + 1, ed);
}
void build(pnode &r, int st, int ed) {
  if (st == ed) {
    r = new node();
    for (int i = 1; i <= maxk; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) r->dp[i][j][k] = hhh[st];
    for (int i = 1; i <= maxk; i++) r->dp[i][0][0] = max(hhh[st], 0);
    return;
  }
  r = new node();
  int mid = (st + ed) >> 1;
  build(r->lch, st, mid);
  build(r->rch, mid + 1, ed);
  update(r, r->lch, r->rch);
}
void change(pnode r, int x, int v, int st, int ed) {
  if (st == ed) {
    for (int i = 1; i <= maxk; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) r->dp[i][j][k] = v;
    for (int i = 1; i <= maxk; i++) r->dp[i][0][0] = max(v, 0);
    return;
  }
  int mid = (st + ed) >> 1;
  if (x <= mid)
    change(r->lch, x, v, st, mid);
  else
    change(r->rch, x, v, mid + 1, ed);
  update(r, r->lch, r->rch);
}
pnode ask(pnode r, int ll, int rr, int st, int ed) {
  pnode ans;
  if (ll == st && rr == ed) {
    ans = new node();
    for (int i = 1; i <= maxk; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) ans->dp[i][j][k] = r->dp[i][j][k];
    return ans;
  }
  bool asd = 0;
  int mid = (st + ed) >> 1;
  if (ll <= mid) {
    ans = ask(r->lch, ll, min(mid, rr), st, mid);
    asd = 1;
  }
  if (rr > mid) {
    if (!asd)
      ans = ask(r->rch, max(ll, mid + 1), rr, mid + 1, ed);
    else {
      update(ans, ans, ask(r->rch, max(ll, mid + 1), rr, mid + 1, ed));
    }
  }
  return ans;
}
int n;
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> hhh[i];
  build(root, 1, n);
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int op;
    cin >> op;
    if (op == 0) {
      int a, v;
      cin >> a >> v;
      change(root, a, v, 1, n);
    } else if (op == 1) {
      int l, r, k;
      cin >> l >> r >> k;
      cout << ask(root, l, r, 1, n)->dp[k][0][0] << endl;
    }
  }
  return 0;
}
