#include <bits/stdc++.h>
using namespace std;
struct node {
  int ken, sag, sol, top;
  int kensag, kensol, solbit, sagbit;
  node(int a = 0, int a2 = 0, int a3 = 0, int a4 = 0, int a5 = 0, int a6 = 0,
       int a7 = 0, int a8 = 0) {
    ken = a;
    sol = a2;
    sag = a3;
    top = a4;
    kensol = a5;
    kensag = a6;
    solbit = a7;
    sagbit = a8;
  }
};
struct aralik {
  int bas, son, u;
  node mal;
  friend bool operator<(const aralik &a, const aralik &b) {
    return a.mal.ken < b.mal.ken;
  }
  aralik(node a = 0, int b = 0, int c = 0, int d = 0) {
    mal = a;
    bas = b;
    son = c;
    u = d;
  }
};
priority_queue<aralik> q;
int a, ar[100020];
node segment[100020 * 5][2];
node merge(node a, node b) {
  if (b.kensol == -1e9) return a;
  if (a.kensol == -1e9) return b;
  node t;
  t.top = a.top + b.top;
  if (a.ken >= b.ken && a.ken >= a.sag + b.sol)
    t.ken = a.ken, t.kensol = a.kensol, t.kensag = a.kensag;
  else if (b.ken >= a.ken && b.ken >= a.sag + b.sol)
    t.ken = b.ken, t.kensol = b.kensol, t.kensag = b.kensag;
  else
    t.ken = a.sag + b.sol, t.kensol = a.sagbit, t.kensag = b.solbit;
  if (a.sol > b.sol + a.top)
    t.sol = a.sol, t.solbit = a.solbit;
  else
    t.sol = b.sol + a.top, t.solbit = b.solbit;
  if (b.sag > a.sag + b.top)
    t.sag = b.sag, t.sagbit = b.sagbit;
  else
    t.sag = a.sag + b.top, t.sagbit = a.sagbit;
  return t;
}
node create(int k, int b, int s, int u) {
  if (b == s) {
    if (ar[b] >= 0)
      return segment[k][u] = node(ar[b], ar[b], ar[b], ar[b], b, b, b, b);
    return segment[k][u] = node(0, 0, 0, ar[b], b + 1, b - 1, b - 1, b + 1);
  }
  return segment[k][u] = merge(create(2 * k, b, (b + s) / 2, u),
                               create(2 * k + 1, (b + s) / 2 + 1, s, u));
}
node update(int k, int b, int s, int x, int m, int u) {
  if (b > x || x > s) return segment[k][u];
  if (b == s) {
    ar[b] = m;
    if (ar[b] >= 0)
      return segment[k][u] = node(ar[b], ar[b], ar[b], ar[b], b, b, b, b);
    return segment[k][u] = node(0, 0, 0, ar[b], b + 1, b - 1, b - 1, b + 1);
  }
  return segment[k][u] = merge(update(2 * k, b, (b + s) / 2, x, m, u),
                               update(2 * k + 1, (b + s) / 2 + 1, s, x, m, u));
}
node find(int k, int b, int s, int x, int y, int u) {
  if (s < x || y < b) return node(0, 0, 0, 0, -1e9, -1e9, -1e9, -1e9);
  if (x <= b && s <= y) return segment[k][u];
  return merge(find(2 * k, b, (b + s) / 2, x, y, u),
               find(2 * k + 1, (b + s) / 2 + 1, s, x, y, u));
}
int main() {
  scanf("%d", &a);
  for (int i = 1; i <= a; i++) scanf("%d", &ar[i]);
  create(1, 1, a, 0);
  for (int i = 1; i <= a; i++) ar[i] *= -1;
  create(1, 1, a, 1);
  int b;
  scanf("%d", &b);
  for (int i = 1; i <= b; i++) {
    int y, j, k, l;
    scanf("%d", &y);
    if (!y) {
      scanf("%d %d", &j, &k);
      update(1, 1, a, j, k, 0);
      update(1, 1, a, j, -k, 1);
    } else {
      scanf("%d %d %d", &j, &k, &l);
      while (!q.empty()) q.pop();
      node w = find(1, 1, a, j, k, 0);
      q.push(aralik(w, j, k, 0));
      int top = 0;
      aralik t;
      for (int m = 1; m <= l && !q.empty(); m++) {
        t = q.top();
        q.pop();
        if (t.mal.kensol <= 0 || t.mal.kensag <= 0) continue;
        if (t.bas <= t.mal.kensol - 1)
          q.push(aralik(find(1, 1, a, t.bas, t.mal.kensol - 1, t.u), t.bas,
                        t.mal.kensol - 1, t.u));
        if (t.mal.kensol <= t.mal.kensag)
          q.push(aralik(find(1, 1, a, t.mal.kensol, t.mal.kensag, !t.u),
                        t.mal.kensol, t.mal.kensag, !t.u));
        if (t.mal.kensag + 1 <= t.son)
          q.push(aralik(find(1, 1, a, t.mal.kensag + 1, t.son, t.u),
                        t.mal.kensag + 1, t.son, t.u));
        top += t.mal.ken;
      }
      printf("%d\n", top);
    }
  }
  return 0;
}
