#include <bits/stdc++.h>
using namespace std;
int ml[100005 * 4], nl[100005 * 4], mr[100005 * 4], nr[100005 * 4],
    lm[100005 * 4], ln[100005 * 4], rm[100005 * 4], rn[100005 * 4],
    sm[100005 * 4], sn[100005 * 4], flag[100005 * 4], sum[100005 * 4];
int a[100005], ql, qr, qk, qw, fl[25], fr[25], lsn[100005 * 4], lsm[100005 * 4],
    rsn[100005 * 4], rsm[100005 * 4], ans, nml, nlm, la, ra;
void push_up(int o) {
  int lc = o << 1, rc = o << 1 | 1;
  if (ml[lc] <= sum[lc] + ml[rc]) {
    ml[o] = sum[lc] + ml[rc];
    lm[o] = lm[rc];
  } else {
    ml[o] = ml[lc];
    lm[o] = lm[lc];
  }
  if (nl[lc] >= sum[lc] + nl[rc]) {
    nl[o] = sum[lc] + nl[rc];
    ln[o] = ln[rc];
  } else {
    nl[o] = nl[lc];
    ln[o] = ln[lc];
  }
  if (mr[rc] <= sum[rc] + mr[lc]) {
    mr[o] = sum[rc] + mr[lc];
    rm[o] = rm[lc];
  } else {
    mr[o] = mr[rc];
    rm[o] = rm[rc];
  }
  if (nr[rc] >= sum[rc] + nr[lc]) {
    nr[o] = sum[rc] + nr[lc];
    rn[o] = rn[lc];
  } else {
    nr[o] = nr[rc];
    rn[o] = rn[rc];
  }
  if (mr[lc] + ml[rc] >= sm[lc] && mr[lc] + ml[rc] >= sm[rc]) {
    sm[o] = mr[lc] + ml[rc];
    lsm[o] = rm[lc];
    rsm[o] = lm[rc];
  } else if (sm[lc] >= sm[rc]) {
    sm[o] = sm[lc];
    lsm[o] = lsm[lc];
    rsm[o] = rsm[lc];
  } else {
    sm[o] = sm[rc];
    lsm[o] = lsm[rc];
    rsm[o] = rsm[rc];
  }
  if (nr[lc] + nl[rc] <= sn[lc] && nr[lc] + nl[rc] <= sn[rc]) {
    sn[o] = nr[lc] + nl[rc];
    lsn[o] = rn[lc];
    rsn[o] = ln[rc];
  } else if (sn[lc] <= sn[rc]) {
    sn[o] = sn[lc];
    lsn[o] = lsn[lc];
    rsn[o] = rsn[lc];
  } else {
    sn[o] = sn[rc];
    lsn[o] = lsn[rc];
    rsn[o] = rsn[rc];
  }
  sum[o] = sum[lc] + sum[rc];
}
void put_flag(int o) {
  flag[o] ^= 1;
  swap(sm[o], sn[o]);
  sm[o] *= -1;
  sn[o] *= -1;
  swap(nl[o], ml[o]);
  swap(nr[o], mr[o]);
  nl[o] *= -1;
  ml[o] *= -1;
  nr[o] *= -1;
  mr[o] *= -1;
  swap(ln[o], lm[o]);
  swap(rn[o], rm[o]);
  swap(lsn[o], lsm[o]);
  swap(rsn[o], rsm[o]);
  sum[o] *= -1;
}
void push_down(int o) {
  if (flag[o]) {
    flag[o] = 0;
    put_flag(o << 1);
    put_flag(o << 1 | 1);
  }
}
void build_tree(int o, int L, int R) {
  if (L == R) {
    ml[o] = a[L];
    mr[o] = a[L];
    nl[o] = a[L];
    nr[o] = a[L];
    lm[o] = L;
    rm[o] = R;
    ln[o] = L;
    rn[o] = R;
    sm[o] = a[L];
    sn[o] = a[L];
    sum[o] = a[L];
    lsm[o] = L;
    rsm[o] = R;
    lsn[o] = L;
    rsn[o] = R;
    return;
  }
  int mid = (L + R) >> 1;
  build_tree(o << 1, L, mid);
  build_tree(o << 1 | 1, mid + 1, R);
  push_up(o);
}
void Change(int o, int L, int R) {
  if (L == R) {
    ml[o] = a[L];
    mr[o] = a[L];
    nl[o] = a[L];
    nr[o] = a[L];
    sm[o] = a[L];
    sn[o] = a[L];
    sum[o] = a[L];
    return;
  }
  push_down(o);
  int mid = (L + R) >> 1;
  if (qk <= mid)
    Change(o << 1, L, mid);
  else
    Change(o << 1 | 1, mid + 1, R);
  push_up(o);
}
void Change2(int o, int L, int R) {
  if (L >= ql && R <= qr) {
    put_flag(o);
    return;
  }
  push_down(o);
  int mid = (L + R) >> 1;
  if (ql <= mid) Change2(o << 1, L, mid);
  if (qr > mid) Change2(o << 1 | 1, mid + 1, R);
  push_up(o);
}
void Query(int o, int L, int R) {
  if (L >= ql && R <= qr) {
    if (sm[o] > ans && sm[o] >= nml + ml[o]) {
      ans = sm[o];
      la = lsm[o];
      ra = rsm[o];
    } else if (nml + ml[o] > ans) {
      ans = nml + ml[o];
      la = nlm;
      ra = lm[o];
    }
    if (mr[o] >= nml + sum[o]) {
      nml = mr[o];
      nlm = rm[o];
    } else {
      nml = nml + sum[o];
    }
    return;
  }
  push_down(o);
  int mid = (L + R) >> 1;
  if (ql <= mid) Query(o << 1, L, mid);
  if (qr > mid) Query(o << 1 | 1, mid + 1, R);
}
int main() {
  int n, m, i, op, sum, l, r;
  cin >> n;
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  build_tree(1, 1, n);
  cin >> m;
  while (m--) {
    scanf("%d", &op);
    if (op == 0) {
      scanf("%d%d", &qk, &qw);
      a[qk] = qw;
      Change(1, 1, n);
    } else {
      scanf("%d%d%d", &l, &r, &qk);
      sum = 0;
      for (i = 1; i <= qk; i++) {
        ans = -1000000000, nml = -1000000000;
        nlm = 0;
        ql = l, qr = r;
        Query(1, 1, n);
        if (ans <= 0)
          break;
        else {
          sum += ans;
          fl[i] = la;
          fr[i] = ra;
          ql = la, qr = ra;
          Change2(1, 1, n);
        }
      }
      printf("%d\n", sum);
      qk = i - 1;
      for (i = 1; i <= qk; i++) {
        ql = fl[i], qr = fr[i];
        Change2(1, 1, n);
      }
    }
  }
  return 0;
}
