#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
struct data {
  int l, r, v;
  data(int L = 0, int R = 0, int V = 0) {
    l = L;
    r = R;
    v = V;
  }
  bool operator<(const data &p) const { return v < p.v; }
  data operator+(const data &p) const { return data(l, p.r, v + p.v); }
};
int n, a[N + 9];
struct tree {
  data sum, ans[2], lans[2], rans[2];
  int rev;
} tr[N * 4 + 9];
void print(data k) { printf("%d %d %d\n", k.l, k.r, k.v); }
void print(tree k) {
  printf("%d\n", k);
  print(k.sum);
  print(k.lans[0]);
  print(k.rans[0]);
  print(k.ans[0]);
  print(k.lans[1]);
  print(k.rans[1]);
  print(k.ans[1]);
}
void print(int k) { print(tr[k]); }
tree Merge(tree a, tree b) {
  tree res;
  res.sum = a.sum + b.sum;
  res.lans[0] = max(a.lans[0], a.sum + b.lans[0]);
  res.lans[1] = min(a.lans[1], a.sum + b.lans[1]);
  res.rans[0] = max(b.rans[0], a.rans[0] + b.sum);
  res.rans[1] = min(b.rans[1], a.rans[1] + b.sum);
  res.ans[0] = max(max(a.ans[0], b.ans[0]), a.rans[0] + b.lans[0]);
  res.ans[1] = min(min(a.ans[1], b.ans[1]), a.rans[1] + b.lans[1]);
  res.rev = 0;
  return res;
}
void Pushup(int k) { tr[k] = Merge(tr[k << 1], tr[k << 1 | 1]); }
void Update(int k, int l, int r, int v) {
  tr[k].sum = data(l, r, v);
  tr[k].lans[0] = max(tr[k].sum, data(l, r - 1, 0));
  tr[k].rans[0] = max(tr[k].sum, data(l + 1, r, 0));
  tr[k].ans[0] = max(tr[k].sum, data(l + 1, r - 1, 0));
  tr[k].lans[1] = min(tr[k].sum, data(l, r - 1, 0));
  tr[k].rans[1] = min(tr[k].sum, data(l + 1, r, 0));
  tr[k].ans[1] = min(tr[k].sum, data(l + 1, r - 1, 0));
}
void Update_rev(int k) {
  tr[k].sum.v = -tr[k].sum.v;
  swap(tr[k].lans[0], tr[k].lans[1]);
  swap(tr[k].rans[0], tr[k].rans[1]);
  swap(tr[k].ans[0], tr[k].ans[1]);
  for (int i = 0; i < 2; ++i) {
    tr[k].lans[i].v = -tr[k].lans[i].v;
    tr[k].rans[i].v = -tr[k].rans[i].v;
    tr[k].ans[i].v = -tr[k].ans[i].v;
  }
  tr[k].rev ^= 1;
}
void Pushdown(int k) {
  if (!tr[k].rev) return;
  Update_rev(k << 1);
  Update_rev(k << 1 | 1);
  tr[k].rev = 0;
}
void Build(int l, int r, int k) {
  if (l == r) {
    Update(k, l, r, a[l]);
    return;
  }
  int mid = l + r >> 1;
  Build(l, mid, k << 1);
  Build(mid + 1, r, k << 1 | 1);
  Pushup(k);
}
void Change(int p, int v, int l, int r, int k) {
  if (l == r) {
    Update(k, l, r, v);
    return;
  }
  int mid = l + r >> 1;
  Pushdown(k);
  p <= mid ? Change(p, v, l, mid, k << 1)
           : Change(p, v, mid + 1, r, k << 1 | 1);
  Pushup(k);
}
void Change_rev(int L, int R, int l, int r, int k) {
  if (L <= l && R >= r) {
    Update_rev(k);
    return;
  }
  int mid = l + r >> 1;
  Pushdown(k);
  if (L <= mid) Change_rev(L, R, l, mid, k << 1);
  if (R > mid) Change_rev(L, R, mid + 1, r, k << 1 | 1);
  Pushup(k);
}
tree Query_ans(int L, int R, int l, int r, int k) {
  if (L <= l && R >= r) return tr[k];
  int mid = l + r >> 1;
  Pushdown(k);
  if (R <= mid)
    return Query_ans(L, R, l, mid, k << 1);
  else if (L > mid)
    return Query_ans(L, R, mid + 1, r, k << 1 | 1);
  else
    return Merge(Query_ans(L, R, l, mid, k << 1),
                 Query_ans(L, R, mid + 1, r, k << 1 | 1));
}
void into() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
}
void work() { Build(1, n, 1); }
stack<int> sl, sr;
void getans() {
  int cq;
  scanf("%d", &cq);
  for (; cq--;) {
    int opt, l, r, m;
    scanf("%d%d%d", &opt, &l, &r);
    if (opt) {
      scanf("%d", &m);
      int ans = 0;
      for (int i = 1; i < m; ++i) {
        tree t = Query_ans(l, r, 1, n, 1);
        ans += t.ans[0].v;
        Change_rev(t.ans[0].l, t.ans[0].r, 1, n, 1);
        sl.push(t.ans[0].l);
        sr.push(t.ans[0].r);
      }
      printf("%d\n", ans + Query_ans(l, r, 1, n, 1).ans[0].v);
      for (int i = 1; i < m; ++i) {
        Change_rev(sl.top(), sr.top(), 1, n, 1);
        sl.pop();
        sr.pop();
      }
    } else
      Change(l, r, 1, n, 1);
  }
}
int main() {
  into();
  work();
  getans();
  return 0;
}
