#include <bits/stdc++.h>
using namespace std;
const int maxn = 410000;
int r[110000];
int lef[maxn], rig[maxn], col[maxn];
int val[maxn][2], a[maxn][2], b[maxn][2], sum[maxn][2];
int lmax[maxn][2], lpos[maxn][2], rmax[maxn][2], rpos[maxn][2];
void down(int idx) {
  col[idx] ^= 1;
  swap(val[idx][0], val[idx][1]);
  swap(a[idx][0], a[idx][1]);
  swap(b[idx][0], b[idx][1]);
  swap(sum[idx][0], sum[idx][1]);
  swap(lmax[idx][0], lmax[idx][1]);
  swap(lpos[idx][0], lpos[idx][1]);
  swap(rmax[idx][0], rmax[idx][1]);
  swap(rpos[idx][0], rpos[idx][1]);
}
void up(int idx) {
  for (int i = 0; i < 2; ++i) {
    val[idx][i] = rmax[idx * 2][i] + lmax[idx * 2 + 1][i];
    a[idx][i] = rpos[idx * 2][i];
    b[idx][i] = lpos[idx * 2 + 1][i];
    if (val[idx][i] < val[idx * 2][i])
      val[idx][i] = val[idx * 2][i], a[idx][i] = a[idx * 2][i],
      b[idx][i] = b[idx * 2][i];
    if (val[idx][i] < val[idx * 2 + 1][i])
      val[idx][i] = val[idx * 2 + 1][i], a[idx][i] = a[idx * 2 + 1][i],
      b[idx][i] = b[idx * 2 + 1][i];
    sum[idx][i] = sum[idx * 2][i] + sum[idx * 2 + 1][i];
    lmax[idx][i] = lmax[idx * 2][i];
    lpos[idx][i] = lpos[idx * 2][i];
    if (lmax[idx][i] < sum[idx * 2][i] + lmax[idx * 2 + 1][i])
      lmax[idx][i] = sum[idx * 2][i] + lmax[idx * 2 + 1][i],
      lpos[idx][i] = lpos[idx * 2 + 1][i];
    rmax[idx][i] = rmax[idx * 2 + 1][i];
    rpos[idx][i] = rpos[idx * 2 + 1][i];
    if (rmax[idx][i] < sum[idx * 2 + 1][i] + rmax[idx * 2][i])
      rmax[idx][i] = sum[idx * 2 + 1][i] + rmax[idx * 2][i],
      rpos[idx][i] = rpos[idx * 2][i];
  }
}
int k, x, y;
void query(int idx, int s[]) {
  int u = lef[idx], v = rig[idx];
  if (x <= u && v <= y) {
    s[0] = val[idx][0];
    s[1] = a[idx][0];
    s[2] = b[idx][0];
    s[3] = sum[idx][0];
    s[4] = lmax[idx][0];
    s[5] = lpos[idx][0];
    s[6] = rmax[idx][0];
    s[7] = rpos[idx][0];
  } else {
    int m = u + (v - u) / 2;
    if (col[idx]) down(idx * 2), down(idx * 2 + 1), col[idx] = 0;
    if (y <= m)
      query(idx * 2, s);
    else if (x > m)
      query(idx * 2 + 1, s);
    else {
      int s1[8], s2[8];
      query(idx * 2, s1);
      query(idx * 2 + 1, s2);
      s[0] = max(max(s1[0], s2[0]), s1[6] + s2[4]);
      if (s[0] == s1[0])
        s[1] = s1[1], s[2] = s1[2];
      else if (s[0] == s2[0])
        s[1] = s2[1], s[2] = s2[2];
      else
        s[1] = s1[7], s[2] = s2[5];
      s[3] = s1[3] + s2[3];
      s[4] = s1[4];
      s[5] = s1[5];
      if (s1[3] + s2[4] > s[4]) s[4] = s1[3] + s2[4], s[5] = s2[5];
      s[6] = s2[6];
      s[7] = s2[7];
      if (s2[3] + s1[6] > s[6]) s[6] = s2[3] + s1[6], s[7] = s1[7];
    }
  }
}
void update(int idx) {
  int u = lef[idx], v = rig[idx];
  if (x <= u && v <= y) {
    if (k > 555)
      down(idx);
    else {
      val[idx][0] = sum[idx][0] = lmax[idx][0] = rmax[idx][0] = k;
      val[idx][1] = sum[idx][1] = lmax[idx][1] = rmax[idx][1] = -k;
    }
  } else {
    int m = u + (v - u) / 2;
    if (col[idx]) down(idx * 2), down(idx * 2 + 1), col[idx] = 0;
    if (x <= m) update(idx * 2);
    if (y > m) update(idx * 2 + 1);
    up(idx);
  }
}
void build(int idx, int u, int v) {
  lef[idx] = u;
  rig[idx] = v;
  col[idx] = 0;
  if (u == v) {
    val[idx][0] = lmax[idx][0] = rmax[idx][0] = sum[idx][0] = r[u];
    val[idx][1] = lmax[idx][1] = rmax[idx][1] = sum[idx][1] = -r[u];
    for (int i = 0; i < 2; ++i)
      a[idx][i] = b[idx][i] = lpos[idx][i] = rpos[idx][i] = v;
  } else {
    int m = u + (v - u) / 2;
    build(idx * 2, u, m);
    build(idx * 2 + 1, m + 1, v);
    up(idx);
  }
}
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &r[i]);
  build(1, 1, n);
  vector<int> vt;
  scanf("%d", &m);
  for (int i = 0, kk, u, v, w; i < m; ++i) {
    int res = 0, s[8];
    vt.clear();
    scanf("%d", &kk);
    if (kk == 0) {
      scanf("%d %d", &x, &k);
      y = x;
      update(1);
    } else {
      scanf("%d %d %d", &u, &v, &w);
      k = 666;
      for (int j = 0; j < w; ++j) {
        x = u;
        y = v;
        query(1, s);
        if (s[0] < 0) break;
        res += s[0];
        x = s[1];
        y = s[2];
        vt.push_back(x);
        vt.push_back(y);
        update(1);
      }
      for (int j = vt.size() - 1; j >= 0; j -= 2)
        x = vt[j - 1], y = vt[j], update(1);
      printf("%d\n", res);
    }
  }
  return 0;
}
