#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x * 10) + (ch - '0');
    ch = getchar();
  }
  return x * f;
}
int a[100005];
bool DBG = true;
namespace SegmentTree {
struct node {
  int sum;
  int l, r;
  int maxs;
  int mins;
  int maxsl;
  int maxsr;
  int minsl;
  int minsr;
  int maxl, minl;
  int maxlp, minlp;
  int maxr, minr;
  int maxrp, minrp;
  bool flag;
} tree[100005 << 2];
inline void sw(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}
inline void re(int &a) { a = -a; }
inline void Rev(int i) {
  re(tree[i].sum);
  sw(tree[i].maxs, tree[i].mins);
  re(tree[i].maxs), re(tree[i].mins);
  sw(tree[i].maxsl, tree[i].minsl);
  sw(tree[i].maxsr, tree[i].minsr);
  sw(tree[i].maxl, tree[i].minl);
  re(tree[i].maxl), re(tree[i].minl);
  sw(tree[i].maxlp, tree[i].minlp);
  sw(tree[i].maxr, tree[i].minr);
  re(tree[i].maxr), re(tree[i].minr);
  sw(tree[i].maxrp, tree[i].minrp);
  tree[i].flag ^= 1;
}
inline void pushdown(int i) {
  if (tree[i].flag) Rev(i << 1), Rev(i << 1 | 1), tree[i].flag = 0;
}
node operator+(const node &A, const node &B) {
  node C;
  C.l = A.l, C.r = B.r;
  C.sum = A.sum + B.sum;
  C.flag = false;
  if (max(A.maxs, B.maxs) > A.maxr + B.maxl) {
    if (A.maxs > B.maxs) {
      C.maxs = A.maxs;
      C.maxsl = A.maxsl;
      C.maxsr = A.maxsr;
    } else {
      C.maxs = B.maxs;
      C.maxsl = B.maxsl;
      C.maxsr = B.maxsr;
    }
  } else {
    C.maxs = A.maxr + B.maxl;
    C.maxsl = A.maxrp;
    C.maxsr = B.maxlp;
  }
  if (min(A.mins, B.mins) < A.minr + B.minl) {
    if (A.mins < B.mins) {
      C.mins = A.mins;
      C.minsl = A.minsl;
      C.minsr = A.minsr;
    } else {
      C.mins = B.mins;
      C.minsl = B.minsl;
      C.minsr = B.minsr;
    }
  } else {
    C.mins = A.minr + B.minl;
    C.minsl = A.minrp;
    C.minsr = B.minlp;
  }
  if (A.sum + B.maxl > A.maxl) {
    C.maxl = A.sum + B.maxl;
    C.maxlp = B.maxlp;
  } else {
    C.maxl = A.maxl;
    C.maxlp = A.maxlp;
  }
  if (A.sum + B.minl < A.minl) {
    C.minl = A.sum + B.minl;
    C.minlp = B.minlp;
  } else {
    C.minl = A.minl;
    C.minlp = A.minlp;
  }
  if (A.maxr + B.sum > B.maxr) {
    C.maxr = A.maxr + B.sum;
    C.maxrp = A.maxrp;
  } else {
    C.maxr = B.maxr;
    C.maxrp = B.maxrp;
  }
  if (A.minr + B.sum < B.minr) {
    C.minr = A.minr + B.sum;
    C.minrp = A.minrp;
  } else {
    C.minr = B.minr;
    C.minrp = B.minrp;
  }
  return C;
}
inline void pushup(int i) {
  bool temp = tree[i].flag;
  tree[i] = tree[i << 1] + tree[i << 1 | 1];
  tree[i].flag = temp;
}
inline void Set(int i, int val) {
  tree[i].sum = tree[i].maxs = tree[i].mins = tree[i].maxl = tree[i].minl =
      tree[i].maxr = tree[i].minr = val;
}
void Build(int l, int r, int i) {
  tree[i].flag = 0;
  if (l == r) {
    tree[i].l = l, tree[i].r = l;
    Set(i, a[l]);
    tree[i].maxsl = tree[i].maxsr = tree[i].minsl = tree[i].minsr =
        tree[i].maxlp = tree[i].minlp = tree[i].maxrp = tree[i].minrp = l;
    return;
  }
  int mid = (l + r) >> 1;
  Build(l, mid, i << 1);
  Build(mid + 1, r, i << 1 | 1);
  pushup(i);
}
node Query(int L, int R, int i) {
  if (L <= tree[i].l && tree[i].r <= R) {
    return tree[i];
  }
  pushdown(i);
  int mid = (tree[i].l + tree[i].r) >> 1;
  if (mid >= R)
    return Query(L, R, i << 1);
  else if (mid < L)
    return Query(L, R, i << 1 | 1);
  else
    return Query(L, R, i << 1) + Query(L, R, i << 1 | 1);
}
void Update(int L, int R, int i) {
  if (L <= tree[i].l && tree[i].r <= R) {
    Rev(i);
    return;
  }
  pushdown(i);
  int mid = (tree[i].l + tree[i].r) >> 1;
  if (mid >= R)
    Update(L, R, i << 1);
  else if (mid < L)
    Update(L, R, i << 1 | 1);
  else
    Update(L, R, i << 1), Update(L, R, i << 1 | 1);
  pushup(i);
}
void Update_pos(int index, int i, int val) {
  if (tree[i].l == tree[i].r) {
    Set(i, tree[i].flag ? -val : val);
    return;
  }
  pushdown(i);
  int mid = (tree[i].l + tree[i].r) >> 1;
  if (index <= mid)
    Update_pos(index, i << 1, val);
  else
    Update_pos(index, i << 1 | 1, val);
  pushup(i);
}
}  // namespace SegmentTree
using namespace SegmentTree;
int L[100005], R[100005];
int main() {
  int n = read();
  for (register int i = 1; i <= n; ++i) {
    a[i] = read();
  }
  Build(1, n, 1);
  int q = read();
  while (q--) {
    int opr = read();
    if (opr == 1) {
      int l = read(), r = read(), k = read();
      int tot = 0, ans = 0;
      for (register int i = 1; i <= k; ++i) {
        node Q = Query(l, r, 1);
        if (Q.maxs <= 0) break;
        ans += Q.maxs;
        L[++tot] = Q.maxsl, R[tot] = Q.maxsr;
        Update(L[tot], R[tot], 1);
      }
      for (register int i = 1; i <= tot; ++i) {
        Update(L[i], R[i], 1);
      }
      printf("%d\n", ans);
    } else {
      int i = read(), val = read();
      Update_pos(i, 1, val);
    }
  }
}
