#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100005, Maxk = 22;
int n, m;
inline int get() {
  bool f = false;
  char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = true;
  int v = ch - 48;
  while (isdigit(ch = getchar())) v = v * 10 + ch - 48;
  return f ? -v : v;
}
struct info {
  int s, t, sum;
  info() {}
  info(int s, int t, int sum) : s(s), t(t), sum(sum) {}
  inline bool operator<(const info &rhs) const { return sum < rhs.sum; }
  inline info operator+(const info &rhs) const {
    return info(s, rhs.t, sum + rhs.sum);
  }
  inline void inv(info &rhs) {
    static int g;
    g = s;
    s = rhs.s;
    rhs.s = g;
    g = t;
    t = rhs.t;
    rhs.t = g;
    g = sum;
    sum = -rhs.sum;
    rhs.sum = -g;
  }
} q[Maxk];
struct node {
  info sum, maxl, maxi, maxr, minl, mini, minr;
  bool flag;
  node *lc, *rc;
  inline void leaf(int p, int a) {
    sum = info(p, p, a);
    if (a >= 0) {
      maxl = maxi = maxr = sum;
      minl = mini = info(p, p - 1, 0);
      minr = info(p + 1, p, 0);
    } else {
      minl = mini = minr = sum;
      maxl = maxi = info(p, p - 1, 0);
      maxr = info(p + 1, p, 0);
    }
  }
  inline void update() {
    sum = lc->sum + rc->sum;
    maxl = max(lc->maxl, lc->sum + rc->maxl);
    maxi = max(lc->maxr + rc->maxl, max(lc->maxi, rc->maxi));
    maxr = max(rc->maxr, lc->maxr + rc->sum);
    minl = min(lc->minl, lc->sum + rc->minl);
    mini = min(lc->minr + rc->minl, min(lc->mini, rc->mini));
    minr = min(rc->minr, lc->minr + rc->sum);
  }
  inline void inv() {
    flag ^= true;
    sum.sum *= -1;
    maxl.inv(minl);
    maxi.inv(mini);
    maxr.inv(minr);
  }
  inline void push_down() {
    if (flag) {
      flag = false;
      lc->inv();
      rc->inv();
    }
  }
} po[Maxn * 2], *pn = po;
class Segment_Tree {
  node *root;
  info ql, qi, qr, qs;
  void build(node *&x, int l, int r) {
    x = ++pn;
    if (l == r) {
      x->leaf(l, get());
      return;
    }
    int mid = (l + r) >> 1;
    build(x->lc, l, mid);
    build(x->rc, mid + 1, r);
    x->update();
  }
  void modify(node *x, int l, int r, int p) {
    if (l == r) {
      x->leaf(p, get());
      return;
    }
    x->push_down();
    int mid = (l + r) >> 1;
    if (p <= mid)
      modify(x->lc, l, mid, p);
    else
      modify(x->rc, mid + 1, r, p);
    x->update();
  }
  void inv(node *x, int l, int r, int s, int t) {
    if (s <= l && t >= r) {
      x->inv();
      return;
    }
    x->push_down();
    int mid = (l + r) >> 1;
    if (s <= mid) inv(x->lc, l, mid, s, t);
    if (t > mid) inv(x->rc, mid + 1, r, s, t);
    x->update();
  }
  void qry(node *x, int l, int r, int s, int t) {
    if (s <= l && t >= r) {
      if (l == s) {
        ql = x->maxl;
        qi = x->maxi;
        qr = x->maxr;
        qs = x->sum;
      } else {
        qi = max(qr + x->maxl, max(qi, x->maxi));
        ql = max(ql, qs + x->maxl);
        qr = max(x->maxr, qr + x->sum);
        qs = qs + x->sum;
      }
      return;
    }
    int mid = (l + r) >> 1;
    x->push_down();
    if (s <= mid) qry(x->lc, l, mid, s, t);
    if (t > mid) qry(x->rc, mid + 1, r, s, t);
  }

 public:
  inline void build() { build(root, 1, n); }
  inline void modify(int pos) { modify(root, 1, n, pos); }
  inline void inv(int s, int t) { inv(root, 1, n, s, t); }
  inline info qry(int s, int t) {
    qry(root, 1, n, s, t);
    return qi;
  }
} tr;
int main() {
  n = get();
  tr.build();
  for (m = get(); m; m--) {
    int opx = get();
    if (opx == 0)
      tr.modify(get());
    else {
      int l = get(), r = get(), k = get(), ans = 0;
      for (int i = 1; i <= k; i++) {
        if (i > 1) tr.inv(q[i - 1].s, q[i - 1].t);
        q[i] = tr.qry(l, r);
        if (q[i].sum > 0) ans += q[i].sum;
        if (i == k || q[i].sum == 0) {
          for (int j = 1; j < i; j++) tr.inv(q[j].s, q[j].t);
          break;
        }
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}
