#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, MAXK = 21;
int n, a[MAXN];
struct data {
  int l, r, v;
  data() {}
  data(int _l, int _r, int _v) { l = _l, r = _r, v = _v; }
  bool operator<(const data &a) const { return v < a.v; }
  data operator+(const data &a) const { return data(l, a.r, v + a.v); }
} q[MAXK];
struct Tnode {
  int ls, rs, Flip;
  data mss, lss, rss, Fmss, Flss, Frss, sum;
} t[MAXN << 2];
struct Tsegtree {
  int root, tot;
  void pushup(int x) {
    int ls = t[x].ls, rs = t[x].rs;
    t[x].sum = t[ls].sum + t[rs].sum;
    t[x].mss = max(max(t[ls].mss, t[rs].mss), t[ls].rss + t[rs].lss);
    t[x].lss = max(t[ls].lss, t[ls].sum + t[rs].lss);
    t[x].rss = max(t[rs].rss, t[ls].rss + t[rs].sum);
    t[x].Fmss = min(min(t[ls].Fmss, t[rs].Fmss), t[ls].Frss + t[rs].Flss);
    t[x].Flss = min(t[ls].Flss, t[ls].sum + t[rs].Flss);
    t[x].Frss = min(t[rs].Frss, t[ls].Frss + t[rs].sum);
  }
  void Flip(int y) {
    t[y].sum.v *= -1;
    t[y].Flip ^= 1;
    swap(t[y].mss, t[y].Fmss);
    t[y].mss.v *= -1, t[y].Fmss.v *= -1;
    swap(t[y].lss, t[y].Flss);
    t[y].lss.v *= -1, t[y].Flss.v *= -1;
    swap(t[y].rss, t[y].Frss);
    t[y].rss.v *= -1, t[y].Frss.v *= -1;
  }
  void pushdown(int x) {
    if (!t[x].Flip) return;
    t[x].Flip = 0;
    Flip(t[x].ls), Flip(t[x].rs);
  }
  void build(int &x, int l, int r) {
    x = ++tot;
    t[x].Flip = 0;
    if (l == r) {
      t[x].mss = t[x].lss = t[x].rss = t[x].Fmss = t[x].Flss = t[x].Frss =
          t[x].sum = data(l, l, a[l]);
      return;
    }
    int mid = (l + r) >> 1;
    build(t[x].ls, l, mid), build(t[x].rs, mid + 1, r);
    pushup(x);
  }
  void init() {
    tot = 0;
    build(root, 1, n);
  }
  void update(int x, int l, int r, int k, int v) {
    if (l == r) {
      t[x].mss = t[x].lss = t[x].rss = t[x].Fmss = t[x].Flss = t[x].Frss =
          t[x].sum = data(l, l, v);
      return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (k <= mid)
      update(t[x].ls, l, mid, k, v);
    else
      update(t[x].rs, mid + 1, r, k, v);
    pushup(x);
  }
  void Flip(int x, int l, int r, int l1, int r1) {
    if (l == l1 && r == r1) {
      Flip(x);
      return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (r1 <= mid)
      Flip(t[x].ls, l, mid, l1, r1);
    else {
      if (l1 > mid)
        Flip(t[x].rs, mid + 1, r, l1, r1);
      else
        Flip(t[x].ls, l, mid, l1, mid), Flip(t[x].rs, mid + 1, r, mid + 1, r1);
    }
    pushup(x);
  }
  void qry(int x, int l, int r, int l1, int r1, data &mss, data &lss, data &rss,
           data &sum) {
    if (l == l1 && r == r1) {
      mss = t[x].mss;
      lss = t[x].lss;
      rss = t[x].rss;
      sum = t[x].sum;
      return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (r1 <= mid)
      qry(t[x].ls, l, mid, l1, r1, mss, lss, rss, sum);
    else {
      if (l1 > mid)
        qry(t[x].rs, mid + 1, r, l1, r1, mss, lss, rss, sum);
      else {
        data Lmss, Llss, Lrss, Lsum, Rmss, Rlss, Rrss, Rsum;
        qry(t[x].ls, l, mid, l1, mid, Lmss, Llss, Lrss, Lsum),
            qry(t[x].rs, mid + 1, r, mid + 1, r1, Rmss, Rlss, Rrss, Rsum);
        mss = max(max(Lmss, Rmss), Lrss + Rlss);
        sum = Lsum + Rsum;
        lss = max(Llss, Lsum + Rlss);
        rss = max(Rrss, Lrss + Rsum);
      }
    }
  }
  void update(int x, int v) { update(root, 1, n, x, v); }
  void Flip(int l, int r) { Flip(root, 1, n, l, r); }
  data qry(int l, int r) {
    data mss, lss, rss, sum;
    qry(root, 1, n, l, r, mss, lss, rss, sum);
    return mss;
  }
} tree;
int get() {
  int f = 0, v = 0;
  char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') break;
  if (ch == '-')
    f = 1;
  else
    v = ch - 48;
  while (isdigit(ch = getchar())) v = v * 10 + ch - 48;
  if (f == 1) return -v;
  return v;
}
int main() {
  n = get();
  for (int i = 1; i <= n; i++) a[i] = get();
  tree.init();
  for (int Q = get(); Q; Q--) {
    int tp = get();
    if (tp) {
      int l = get(), r = get(), k = get(), res = 0, cnt = 0;
      data tmp;
      while (cnt < k) {
        tmp = tree.qry(l, r);
        if (tmp.v <= 0) break;
        q[++cnt] = tmp;
        res += tmp.v;
        tree.Flip(tmp.l, tmp.r);
      }
      printf("%d\n", res);
      for (; cnt; cnt--) tree.Flip(q[cnt].l, q[cnt].r);
    } else {
      int x = get(), v = get();
      tree.update(x, v);
    }
  }
  return 0;
}
