#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T &x) {
  char c;
  bool op = 0;
  while (c = getchar(), c < '0' || c > '9')
    if (c == '-') op = 1;
  x = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0';
  if (op) x = -x;
}
template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar('0' + x % 10);
}
const int N = 100005, INF = 0x3f3f3f3f;
int n, m, a[N];
struct data {
  int lx, rx, sum, mx, lp, rp, p1, p2;
  void init(int pos, int val) {
    lp = rp = p1 = p2 = pos;
    lx = rx = mx = sum = val;
  }
};
struct seg {
  bool rev;
  data mn, mx;
  void init(int pos, int val) {
    mn.init(pos, -val);
    mx.init(pos, val);
  }
  void rever() {
    swap(mn, mx);
    rev ^= 1;
  }
} t[4 * N];
void pushdown(int k) {
  if (!t[k].rev) return;
  t[k << 1].rever(), t[k << 1 | 1].rever();
  t[k].rev = 0;
}
void merge(data &c, const data &a, const data &b) {
  c.sum = a.sum + b.sum;
  if (a.sum + b.lx > a.lx)
    c.lx = a.sum + b.lx, c.lp = b.lp;
  else
    c.lx = a.lx, c.lp = a.lp;
  if (b.sum + a.rx > b.rx)
    c.rx = b.sum + a.rx, c.rp = a.rp;
  else
    c.rx = b.rx, c.rp = b.rp;
  c.mx = a.rx + b.lx, c.p1 = a.rp, c.p2 = b.lp;
  if (c.mx < a.mx) c.mx = a.mx, c.p1 = a.p1, c.p2 = a.p2;
  if (c.mx < b.mx) c.mx = b.mx, c.p1 = b.p1, c.p2 = b.p2;
}
void pushup(int k) {
  merge(t[k].mn, t[k << 1].mn, t[k << 1 | 1].mn);
  merge(t[k].mx, t[k << 1].mx, t[k << 1 | 1].mx);
}
void build(int k, int l, int r) {
  if (l == r) return t[k].init(l, a[l]);
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  pushup(k);
}
void rever(int k, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) return t[k].rever();
  pushdown(k);
  int mid = (l + r) >> 1;
  if (ql <= mid) rever(k << 1, l, mid, ql, qr);
  if (qr > mid) rever(k << 1 | 1, mid + 1, r, ql, qr);
  pushup(k);
}
data query(int k, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) return t[k].mx;
  pushdown(k);
  int mid = (l + r) >> 1;
  if (qr <= mid) return query(k << 1, l, mid, ql, qr);
  if (ql > mid) return query(k << 1 | 1, mid + 1, r, ql, qr);
  data ret;
  merge(ret, query(k << 1, l, mid, ql, qr),
        query(k << 1 | 1, mid + 1, r, ql, qr));
  return ret;
}
void change(int k, int l, int r, int p, int x) {
  if (l == r) return t[k].init(p, x);
  pushdown(k);
  int mid = (l + r) >> 1;
  if (p <= mid)
    change(k << 1, l, mid, p, x);
  else
    change(k << 1 | 1, mid + 1, r, p, x);
  pushup(k);
}
void solve(int l, int r, int k) {
  static pair<int, int> stk[N];
  int top = 0, ret = 0;
  data tmp;
  while (k--) {
    tmp = query(1, 1, n, l, r);
    if (tmp.mx < 0) break;
    ret += tmp.mx;
    rever(1, 1, n, tmp.p1, tmp.p2);
    stk[++top] = make_pair(tmp.p1, tmp.p2);
  }
  while (top) rever(1, 1, n, stk[top].first, stk[top].second), top--;
  write(ret), putchar('\n');
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]);
  build(1, 1, n);
  int op, a, b, c;
  read(m);
  while (m--) {
    read(op), read(a), read(b);
    if (op == 0)
      change(1, 1, n, a, b);
    else
      read(c), solve(a, b, c);
  }
  return 0;
}
