#include <bits/stdc++.h>
using namespace std;
const int Inf = 101000;
int tot, n, root, a[1001000], temp, tx, ty, rx, rxl;
struct Node {
  int lc, rc, x, y, X, Y, l, r, L, R, minx, maxn, lmax, rmax, lmin, rmin, sum,
      tag;
} tree[1001000];
pair<int, int> key[1111];
void update(int p, int lc, int rc) {
  tree[p].sum = tree[lc].sum + tree[rc].sum;
  int t = (tree[lc].maxn > tree[rc].maxn) ? lc : rc;
  if (tree[lc].rmax + tree[rc].lmax > tree[t].maxn) {
    tree[p].maxn = tree[lc].rmax + tree[rc].lmax;
    tree[p].X = tree[lc].x;
    tree[p].Y = tree[rc].y;
  } else {
    tree[p].maxn = tree[t].maxn;
    tree[p].X = tree[t].X;
    tree[p].Y = tree[t].Y;
  }
  if (tree[lc].lmax > tree[lc].sum + tree[rc].lmax) {
    tree[p].lmax = tree[lc].lmax;
    tree[p].y = tree[lc].y;
  } else {
    tree[p].lmax = tree[lc].sum + tree[rc].lmax;
    tree[p].y = tree[rc].y;
  }
  if (tree[rc].rmax > tree[rc].sum + tree[lc].rmax) {
    tree[p].rmax = tree[rc].rmax;
    tree[p].x = tree[rc].x;
  } else {
    tree[p].rmax = tree[rc].sum + tree[lc].rmax;
    tree[p].x = tree[lc].x;
  }
  t = (tree[lc].minx < tree[rc].minx) ? lc : rc;
  if (tree[lc].rmin + tree[rc].lmin < tree[t].minx) {
    tree[p].minx = tree[lc].rmin + tree[rc].lmin;
    tree[p].L = tree[lc].l;
    tree[p].R = tree[rc].r;
  } else {
    tree[p].minx = tree[t].minx;
    tree[p].L = tree[t].L;
    tree[p].R = tree[t].R;
  }
  if (tree[lc].lmin < tree[lc].sum + tree[rc].lmin) {
    tree[p].lmin = tree[lc].lmin;
    tree[p].r = tree[lc].r;
  } else {
    tree[p].lmin = tree[lc].sum + tree[rc].lmin;
    tree[p].r = tree[rc].r;
  }
  if (tree[rc].rmin < tree[rc].sum + tree[lc].rmin) {
    tree[p].rmin = tree[rc].rmin;
    tree[p].l = tree[rc].l;
  } else {
    tree[p].rmin = tree[rc].sum + tree[lc].rmin;
    tree[p].l = tree[lc].l;
  }
}
void push(int p, int l, int r) {
  swap(tree[p].maxn, tree[p].minx);
  swap(tree[p].lmax, tree[p].lmin);
  swap(tree[p].rmax, tree[p].rmin);
  swap(tree[p].x, tree[p].l);
  swap(tree[p].y, tree[p].r);
  swap(tree[p].X, tree[p].L);
  swap(tree[p].Y, tree[p].R);
  tree[p].maxn *= -1;
  tree[p].lmax *= -1;
  tree[p].rmax *= -1;
  tree[p].minx *= -1;
  tree[p].lmin *= -1;
  tree[p].rmin *= -1;
  tree[p].sum *= -1;
  tree[p].tag *= -1;
  if (tree[p].lc) tree[tree[p].lc].tag *= -1;
  if (tree[p].rc) tree[tree[p].rc].tag *= -1;
}
int build(int l, int r) {
  int p = ++tot;
  tree[p].tag = -Inf;
  if (l == r) {
    tree[p].lc = tree[p].rc = 0;
    tree[p].sum = a[l];
    tree[p].lmax = tree[p].rmax = tree[p].maxn = a[l];
    tree[p].x = tree[p].y = tree[p].X = tree[p].Y = l;
    tree[p].lmin = tree[p].rmin = tree[p].minx = a[l];
    tree[p].l = tree[p].r = tree[p].L = tree[p].R = l;
  } else {
    int mid = (l + r) >> 1;
    tree[p].lc = build(l, mid);
    tree[p].rc = build(mid + 1, r);
    update(p, tree[p].lc, tree[p].rc);
  }
  return p;
}
void ins(int p, int x, int y, int z, int l, int r) {
  if (tree[p].tag != -Inf) push(p, l, r);
  if (x <= l && r <= y)
    tree[p].tag *= -1;
  else {
    int mid = (l + r) >> 1;
    if (x <= mid) ins(tree[p].lc, x, y, z, l, mid);
    if (y > mid) ins(tree[p].rc, x, y, z, mid + 1, r);
    if (tree[p].lc && tree[tree[p].lc].tag != -Inf) push(tree[p].lc, l, mid);
    if (tree[p].rc && tree[tree[p].rc].tag != -Inf)
      push(tree[p].rc, mid + 1, r);
    update(p, tree[p].lc, tree[p].rc);
  }
}
void change(int p, int x, int y, int l, int r) {
  if (tree[p].tag != -Inf) push(p, l, r);
  if (l == r && l == x) {
    tree[p].sum = y;
    tree[p].lmax = tree[p].rmax = tree[p].maxn = y;
    tree[p].lmin = tree[p].rmin = tree[p].minx = y;
  } else {
    int mid = (l + r) >> 1;
    if (x <= mid)
      change(tree[p].lc, x, y, l, mid);
    else
      change(tree[p].rc, x, y, mid + 1, r);
    if (tree[p].lc && tree[tree[p].lc].tag != -Inf) push(tree[p].lc, l, mid);
    if (tree[p].rc && tree[tree[p].rc].tag != -Inf)
      push(tree[p].rc, mid + 1, r);
    update(p, tree[p].lc, tree[p].rc);
  }
}
void merge(int p) {
  if (tx == -1) {
    temp = tree[p].maxn;
    rx = tree[p].rmax;
    rxl = tree[p].x;
    tx = tree[p].X;
    ty = tree[p].Y;
  } else {
    if (max(tree[p].maxn, tree[p].lmax + rx) > temp) {
      if (tree[p].maxn > tree[p].lmax + rx) {
        temp = tree[p].maxn;
        tx = tree[p].X;
        ty = tree[p].Y;
      } else {
        temp = tree[p].lmax + rx;
        tx = rxl;
        ty = tree[p].y;
      }
    }
    if (tree[p].rmax > tree[p].sum + rx) {
      rx = tree[p].rmax;
      rxl = tree[p].x;
    } else
      rx += tree[p].sum;
  }
}
void query(int p, int x, int y, int l, int r) {
  if (tree[p].tag != -Inf) push(p, l, r);
  if (x <= l && r <= y)
    merge(p);
  else {
    int mid = (l + r) >> 1;
    if (x <= mid) query(tree[p].lc, x, y, l, mid);
    if (y > mid) query(tree[p].rc, x, y, mid + 1, r);
    if (tree[p].lc && tree[tree[p].lc].tag != -Inf) push(tree[p].lc, l, mid);
    if (tree[p].rc && tree[tree[p].rc].tag != -Inf)
      push(tree[p].rc, mid + 1, r);
    update(p, tree[p].lc, tree[p].rc);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  tot = 0;
  root = build(1, n);
  int T;
  for (scanf("%d", &T); T; T--) {
    int opt, L, R, x;
    scanf("%d", &opt);
    if (opt) {
      scanf("%d%d%d", &L, &R, &x);
      int ans = 0, t = 0;
      for (int i = 1; i <= x; i++) {
        temp = -1;
        rxl = rx = tx = ty = 0;
        query(root, L, R, 1, n);
        if (temp >= 0) {
          ans += temp;
          key[i] = make_pair(tx, ty);
          ins(root, tx, ty, Inf, 1, n);
        } else
          break;
        t = i;
      }
      printf("%d\n", ans);
      for (int i = t; i; i--) ins(root, key[i].first, key[i].second, Inf, 1, n);
    } else {
      scanf("%d%d", &L, &x);
      change(root, L, x, 1, n);
    }
  }
  return 0;
}
