#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
struct P {
  int l, r, mid, mi, mx, f, l1, r1, l2, r2, ld1, ld2, rd1, rd2, lv1, lv2, rv1,
      rv2, tot;
} arr[4 * N];
void swap(int &x, int &y) { x ^= y ^= x ^= y; }
void fswap(int &x, int &y) {
  int t = x;
  x = -y;
  y = -t;
}
void fan(int c) {
  arr[c].f ^= 1;
  arr[c].tot *= -1;
  fswap(arr[c].mi, arr[c].mx);
  swap(arr[c].l1, arr[c].l2);
  swap(arr[c].r1, arr[c].r2);
  fswap(arr[c].lv1, arr[c].lv2);
  swap(arr[c].ld1, arr[c].ld2);
  fswap(arr[c].rv1, arr[c].rv2);
  swap(arr[c].rd1, arr[c].rd2);
}
void down(int c) {
  if (arr[c].f) {
    fan(c + c);
    fan(c + c + 1);
    arr[c].f = 0;
  }
}
void up(int c) {
  arr[c].tot = arr[c + c].tot + arr[c + c + 1].tot;
  int mv = arr[c + c].rv2 + arr[c + c + 1].lv2;
  if (arr[c + c].mx >= arr[c + c + 1].mx && arr[c + c].mx >= mv) {
    arr[c].mx = arr[c + c].mx;
    arr[c].l2 = arr[c + c].l2;
    arr[c].r2 = arr[c + c].r2;
  } else if (arr[c + c + 1].mx >= arr[c + c].mx && arr[c + c + 1].mx >= mv) {
    arr[c].mx = arr[c + c + 1].mx;
    arr[c].l2 = arr[c + c + 1].l2;
    arr[c].r2 = arr[c + c + 1].r2;
  } else {
    arr[c].mx = mv;
    arr[c].l2 = arr[c + c].rd2;
    arr[c].r2 = arr[c + c + 1].ld2;
  }
  mv = arr[c + c].rv1 + arr[c + c + 1].lv1;
  if (arr[c + c].mi <= arr[c + c + 1].mi && arr[c + c].mi <= mv) {
    arr[c].mi = arr[c + c].mi;
    arr[c].l1 = arr[c + c].l1;
    arr[c].r1 = arr[c + c].r1;
  } else if (arr[c + c + 1].mi <= arr[c + c].mi && arr[c + c + 1].mi <= mv) {
    arr[c].mi = arr[c + c + 1].mi;
    arr[c].l1 = arr[c + c + 1].l1;
    arr[c].r1 = arr[c + c + 1].r1;
  } else {
    arr[c].mi = mv;
    arr[c].l1 = arr[c + c].rd1;
    arr[c].r1 = arr[c + c + 1].ld1;
  }
  if (arr[c + c].lv1 < arr[c + c].tot + arr[c + c + 1].lv1) {
    arr[c].lv1 = arr[c + c].lv1;
    arr[c].ld1 = arr[c + c].ld1;
  } else {
    arr[c].lv1 = arr[c + c].tot + arr[c + c + 1].lv1;
    arr[c].ld1 = arr[c + c + 1].ld1;
  }
  if (arr[c + c].lv2 > arr[c + c].tot + arr[c + c + 1].lv2) {
    arr[c].lv2 = arr[c + c].lv2;
    arr[c].ld2 = arr[c + c].ld2;
  } else {
    arr[c].lv2 = arr[c + c].tot + arr[c + c + 1].lv2;
    arr[c].ld2 = arr[c + c + 1].ld2;
  }
  if (arr[c + c + 1].rv1 < arr[c + c + 1].tot + arr[c + c].rv1) {
    arr[c].rv1 = arr[c + c + 1].rv1;
    arr[c].rd1 = arr[c + c + 1].rd1;
  } else {
    arr[c].rv1 = arr[c + c + 1].tot + arr[c + c].rv1;
    arr[c].rd1 = arr[c + c].rd1;
  }
  if (arr[c + c + 1].rv2 > arr[c + c + 1].tot + arr[c + c].rv2) {
    arr[c].rv2 = arr[c + c + 1].rv2;
    arr[c].rd2 = arr[c + c + 1].rd2;
  } else {
    arr[c].rv2 = arr[c + c + 1].tot + arr[c + c].rv2;
    arr[c].rd2 = arr[c + c].rd2;
  }
}
void build(int L, int R, int c) {
  arr[c].l = L;
  arr[c].r = R;
  arr[c].mid = (L + R) / 2;
  if (L == R) {
    arr[c].tot = arr[c].lv1 = arr[c].lv2 = arr[c].rv1 = arr[c].rv2 = arr[c].mi =
        arr[c].mx = a[L];
    arr[c].ld1 = arr[c].ld2 = arr[c].rd1 = arr[c].rd2 = arr[c].l1 = arr[c].r1 =
        arr[c].l2 = arr[c].r2 = L;
    return;
  }
  build(L, arr[c].mid, c + c);
  build(arr[c].mid + 1, R, c + c + 1);
  up(c);
}
void rev(int L, int R, int c) {
  if (L <= arr[c].l && R >= arr[c].r) {
    fan(c);
    return;
  }
  down(c);
  if (L <= arr[c].mid) rev(L, R, c + c);
  if (R > arr[c].mid) rev(L, R, c + c + 1);
  up(c);
}
int rt, ld = -1, rd, pr, pv;
void find(int L, int R, int c) {
  if (L <= arr[c].l && R >= arr[c].r) {
    if (ld == -1) {
      ld = arr[c].l2;
      rd = arr[c].r2;
      rt = arr[c].mx;
      pr = arr[c].rd2;
      pv = arr[c].rv2;
    } else {
      if (arr[c].mx > pv + arr[c].lv2) {
        if (arr[c].mx > rt) {
          rt = arr[c].mx;
          ld = arr[c].l2;
          rd = arr[c].r2;
        }
      } else {
        if (pv + arr[c].lv2 > rt) {
          rt = pv + arr[c].lv2;
          ld = pr;
          rd = arr[c].ld2;
        }
      }
      if (arr[c].rv2 > arr[c].tot + pv) {
        pv = arr[c].rv2;
        pr = arr[c].rd2;
      } else {
        pv += arr[c].tot;
      }
    }
    return;
  }
  down(c);
  if (L <= arr[c].mid) find(L, R, c + c);
  if (R > arr[c].mid) find(L, R, c + c + 1);
}
void update(int x, int v, int c) {
  if (arr[c].l == arr[c].r) {
    arr[c].tot = arr[c].lv1 = arr[c].lv2 = arr[c].rv1 = arr[c].rv2 = arr[c].mi =
        arr[c].mx = v;
    return;
  }
  down(c);
  if (x <= arr[c].mid)
    update(x, v, c + c);
  else
    update(x, v, c + c + 1);
  up(c);
}
int work(int l, int r, int k) {
  if (!k) return 0;
  ld = -1;
  find(l, r, 1);
  if (rt <= 0) return 0;
  int ret = rt, ll = ld, rr = rd;
  rev(ld, rd, 1);
  ret += work(l, r, k - 1);
  rev(ll, rr, 1);
  return ret;
}
int main() {
  int n, m, i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, n, 1);
  scanf("%d", &m);
  while (m--) {
    int t;
    scanf("%d", &t);
    if (!t) {
      int x, v;
      scanf("%d%d", &x, &v);
      update(x, v, 1);
    } else {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      printf("%d\n", work(l, r, k));
    }
  }
  return 0;
}
