#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
bool lz[N * 4], flg;
int a[N], b[N];
inline int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
struct Dat {
  int ls, rs, sz, tr, l, r, p, q;
  inline void init(int x, int y) {
    sz = x;
    if (x < 0)
      tr = ls = rs = 0, l = y + 1, r = y, p = y - 1, q = y + 1;
    else
      tr = ls = rs = x, l = r = p = q = y;
  }
  inline void merge(Dat &A, Dat &B) {
    if (A.sz + B.ls > A.ls)
      ls = A.sz + B.ls, p = B.p;
    else
      ls = A.ls, p = A.p;
    if (A.rs + B.sz > B.rs)
      rs = A.rs + B.sz, q = A.q;
    else
      rs = B.rs, q = B.q;
    sz = A.sz + B.sz;
    int s1 = A.tr, s2 = B.tr, s3 = A.rs + B.ls;
    if (s1 > s2) {
      if (s1 > s3)
        tr = s1, l = A.l, r = A.r;
      else
        tr = s3, l = A.q, r = B.p;
    } else {
      if (s2 > s3)
        tr = s2, l = B.l, r = B.r;
      else
        tr = s3, l = A.q, r = B.p;
    }
  }
} s1[N * 4], s2[N * 4], ret, tmp;
inline void pushup(int o) {
  s1[o].merge(s1[o << 1], s1[o << 1 | 1]);
  s2[o].merge(s2[o << 1], s2[o << 1 | 1]);
}
inline void pushdown(int o) {
  lz[o << 1] ^= 1, lz[o << 1 | 1] ^= 1, lz[o] = 0;
  swap(s1[o << 1], s2[o << 1]), swap(s1[o << 1 | 1], s2[o << 1 | 1]);
}
inline void build(int l, int r, int o) {
  if (l == r) {
    int x = gi();
    s1[o].init(x, l), s2[o].init(-x, l);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, o << 1), build(mid + 1, r, o << 1 | 1);
  pushup(o);
}
inline void insert(int l, int r, int p, int z, int o) {
  if (l == r) {
    s1[o].init(z, l), s2[o].init(-z, l);
    return;
  }
  if (lz[o]) pushdown(o);
  int mid = (l + r) >> 1;
  if (p <= mid)
    insert(l, mid, p, z, o << 1);
  else
    insert(mid + 1, r, p, z, o << 1 | 1);
  pushup(o);
}
inline void update(int l, int r, int L, int R, int o) {
  if (L <= l && r <= R) {
    swap(s1[o], s2[o]), lz[o] ^= 1;
    return;
  }
  if (lz[o]) pushdown(o);
  int mid = (l + r) >> 1;
  if (R <= mid)
    update(l, mid, L, R, o << 1);
  else if (L > mid)
    update(mid + 1, r, L, R, o << 1 | 1);
  else
    update(l, mid, L, mid, o << 1), update(mid + 1, r, mid + 1, R, o << 1 | 1);
  pushup(o);
}
inline void query(int l, int r, int L, int R, int o) {
  if (L <= l && r <= R) {
    if (!flg)
      ret = s1[o], flg = 1;
    else
      tmp = ret, ret.merge(tmp, s1[o]);
    return;
  }
  if (lz[o]) pushdown(o);
  int mid = (l + r) >> 1;
  if (R <= mid)
    query(l, mid, L, R, o << 1);
  else if (L > mid)
    query(mid + 1, r, L, R, o << 1 | 1);
  else
    query(l, mid, L, mid, o << 1), query(mid + 1, r, mid + 1, R, o << 1 | 1);
  pushup(o);
}
int main() {
  int n, m;
  cin >> n;
  build(1, n, 1);
  cin >> m;
  while (m--) {
    int op = gi(), l = gi(), r = gi();
    if (!op)
      insert(1, n, l, r, 1);
    else {
      int k = gi(), ans = 0;
      for (int i = 1; i <= k; i++) {
        flg = 0, query(1, n, l, r, 1);
        ans += ret.tr, a[i] = ret.l, b[i] = ret.r;
        if (a[i] <= b[i]) update(1, n, a[i], b[i], 1);
      }
      while (k) {
        if (a[k] <= b[k]) update(1, n, a[k], b[k], 1);
        --k;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}
