#include <bits/stdc++.h>
using namespace std;
template <typename T>
void Read(T &cn) {
  char c;
  int sig = 1;
  while (!isdigit(c = getchar()))
    if (c == '-') sig = -1;
  cn = c - 48;
  while (isdigit(c = getchar())) cn = cn * 10 + c - 48;
  cn *= sig;
}
template <typename T>
void Write(T cn) {
  if (cn < 0) {
    putchar('-');
    cn = 0 - cn;
  }
  int wei = 0;
  T cm = 0;
  int cx = cn % 10;
  cn /= 10;
  while (cn) wei++, cm = cm * 10 + cn % 10, cn /= 10;
  while (wei--) putchar(cm % 10 + 48), cm /= 10;
  putchar(cx + 48);
}
struct qwe {
  int l, r;
};
struct dan {
  int l, r, ans;
};
struct dx {
  int zuo, you, da, he;
  int l, r, z, y;
};
dan mk(int cn, int cm, int cx) {
  dan guo;
  guo.l = cn;
  guo.r = cm;
  guo.ans = cx;
  return guo;
}
struct Seg {
  struct node {
    dx d, x;
    int p;
  };
  node t[100000 * 4 + 1];
  void zhuang(dx &cn, int cm, int cx) {
    cn.zuo = cn.you = cn.da = cn.he = cm;
    cn.l = cn.r = cn.z = cn.y = cx;
  }
  void build(int cn, int l, int r, int a[]) {
    t[cn].p = 0;
    if (l == r) {
      zhuang(t[cn].d, a[l], l);
      zhuang(t[cn].x, -a[l], l);
      return;
    }
    build(cn << 1, l, (l + r) >> 1, a);
    build((cn << 1) | 1, ((l + r) >> 1) + 1, r, a);
    update(cn, (l + r) >> 1);
  }
  void r_update(dx &cn, dx ls, dx rs, int zh) {
    cn.he = ls.he + rs.he;
    if (ls.da > rs.da)
      cn.da = ls.da, cn.l = ls.l, cn.r = ls.r;
    else
      cn.da = rs.da, cn.l = rs.l, cn.r = rs.r;
    if (cn.da < ls.you + rs.zuo)
      cn.da = ls.you + rs.zuo, cn.l = ls.y, cn.r = rs.z;
    if (ls.zuo > ls.he + rs.zuo)
      cn.zuo = ls.zuo, cn.z = ls.z;
    else
      cn.zuo = ls.he + rs.zuo, cn.z = rs.z;
    if (cn.zuo < ls.he) cn.zuo = ls.he, cn.z = zh;
    if (rs.you > rs.he + ls.you)
      cn.you = rs.you, cn.y = rs.y;
    else
      cn.you = rs.he + ls.you, cn.y = ls.y;
    if (cn.you < rs.he) cn.you = rs.he, cn.y = zh + 1;
  }
  void update(int cn, int zh) {
    int ls = cn << 1, rs = ls + 1;
    r_update(t[cn].d, t[ls].d, t[rs].d, zh);
    r_update(t[cn].x, t[ls].x, t[rs].x, zh);
  }
  void tui(int cn) {
    if (!t[cn].p) return;
    int ls = cn << 1, rs = (cn << 1) | 1;
    t[ls].p ^= 1;
    swap(t[ls].d, t[ls].x);
    t[rs].p ^= 1;
    swap(t[rs].d, t[rs].x);
    t[cn].p = 0;
  }
  void gai(int cn, int cm, int cx, int l, int r) {
    if (l == r) {
      zhuang(t[cn].d, cx, l);
      zhuang(t[cn].x, -cx, l);
      return;
    }
    tui(cn);
    int zh = (l + r) >> 1;
    if (cm <= zh)
      gai(cn << 1, cm, cx, l, zh);
    else
      gai((cn << 1) | 1, cm, cx, zh + 1, r);
    update(cn, (l + r) >> 1);
  }
  void qufan(int cn, int cl, int cr, int l, int r) {
    if (cl <= l && r <= cr) {
      dx lin = t[cn].d;
      t[cn].d = t[cn].x;
      t[cn].x = lin;
      t[cn].p ^= 1;
      return;
    }
    tui(cn);
    int zh = (l + r) >> 1;
    if (cl <= zh) qufan(cn << 1, cl, cr, l, zh);
    if (cr > zh) qufan((cn << 1) | 1, cl, cr, zh + 1, r);
    update(cn, (l + r) >> 1);
  }
  dx xun(int cn, int cl, int cr, int l, int r) {
    if (cl <= l && r <= cr) return t[cn].d;
    tui(cn);
    int zh = (l + r) >> 1;
    if (cl <= zh) {
      dx guo = xun(cn << 1, cl, cr, l, zh);
      if (cr > zh) {
        dx guo2 = xun((cn << 1) | 1, cl, cr, zh + 1, r);
        r_update(guo, guo, guo2, zh);
      }
      return guo;
    }
    if (cr > zh) return xun((cn << 1) | 1, cl, cr, zh + 1, r);
  }
} T;
int n, q;
int a[100000 + 1];
qwe zhan[100000 + 1];
int zlen;
int main() {
  Read(n);
  for (int i = 1; i <= n; i++) Read(a[i]);
  T.build(1, 1, n, a);
  Read(q);
  for (int i = 1; i <= q; i++) {
    int bx, bn, bm, by;
    Read(bx);
    Read(bn);
    Read(bm);
    if (!bx)
      T.gai(1, bn, bm, 1, n);
    else {
      Read(by);
      zlen = 0;
      long long guo = 0;
      for (int j = 1; j <= by; j++) {
        dx lin = T.xun(1, bn, bm, 1, n);
        if (lin.da <= 0) break;
        guo += lin.da;
        zhan[++zlen].l = lin.l;
        zhan[zlen].r = lin.r;
        T.qufan(1, lin.l, lin.r, 1, n);
      }
      for (int j = 1; j <= zlen; j++) T.qufan(1, zhan[j].l, zhan[j].r, 1, n);
      Write(guo);
      putchar('\n');
    }
  }
  return 0;
}
