#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmin(T &a, T b) {
  a = min(a, b);
}
template <typename T>
void chkmax(T &a, T b) {
  a = max(a, b);
}
inline int fread(void) {
  int ret = 0, op = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') op = -1;
  for (; isdigit(ch); ch = getchar()) ret = (ret << 1) + (ret << 3) - '0' + ch;
  return ret * op;
}
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int MAXM = +10;
int a[MAXN], n, Q;
struct Tuple {
  int l, r, val;
  Tuple() { l = INF, r = -INF, val = 0; }
  Tuple(int _val) { l = INF, r = -INF, val = _val; }
  Tuple(int _l, int _r, int _val) : l(_l), r(_r), val(_val) {}
  Tuple operator+(Tuple &b) {
    return Tuple(min(l, b.l), max(r, b.r), val + b.val);
  }
  bool operator<(const Tuple &b) const { return val < b.val; }
  bool operator>(const Tuple &b) const { return val > b.val; }
};
Tuple operator+(const Tuple &a, const Tuple &b) {
  return Tuple(min(a.l, b.l), max(a.r, b.r), a.val + b.val);
}
struct Node {
  Tuple lmax, rmax, lmin, rmin, sum, maxw, minw;
  Node() {
    lmax = Tuple(-INF);
    rmax = maxw = lmax;
    lmin = Tuple(INF);
    rmin = minw = lmin;
    sum = Tuple(0);
  }
  Node(int _pos, int _val) {
    lmax = Tuple(_pos, _pos, _val);
    rmax = lmin = rmin = sum = maxw = minw = lmax;
  }
};
Node operator+(const Node x, const Node y) {
  Node ret(0, 0);
  ret.lmax = max(x.lmax, x.sum + y.lmax);
  ret.lmin = min(x.lmin, x.sum + y.lmin);
  ret.rmax = max(y.rmax, y.sum + x.rmax);
  ret.rmin = min(y.rmin, y.sum + x.rmin);
  ret.sum = x.sum + y.sum;
  ret.maxw = max(max(x.maxw, y.maxw), x.rmax + y.lmax);
  ret.minw = min(min(x.minw, y.minw), x.rmin + y.lmin);
  return ret;
}
Node t[MAXN << 2];
int rev[MAXN << 2];
void pushup(int x) { t[x] = t[(x << 1)] + t[(x << 1 | 1)]; }
void reverse(int x) {
  swap(t[x].lmax, t[x].lmin);
  swap(t[x].rmax, t[x].rmin);
  swap(t[x].maxw, t[x].minw);
  t[x].lmax.val *= -1;
  t[x].lmin.val *= -1;
  t[x].rmax.val *= -1;
  t[x].rmin.val *= -1;
  t[x].maxw.val *= -1;
  t[x].minw.val *= -1;
  t[x].sum.val *= -1;
}
void pushdown(int x) {
  if (!rev[x]) return;
  rev[(x << 1)] ^= 1;
  rev[(x << 1 | 1)] ^= 1;
  reverse((x << 1));
  reverse((x << 1 | 1));
  rev[x] = 0;
}
void build(int x, int l, int r) {
  if (l == r) {
    t[x] = Node(l, a[l]);
    rev[x] = 0;
    return;
  }
  build((x << 1), l, ((l + r) >> 1));
  build((x << 1 | 1), ((l + r) >> 1) + 1, r);
  pushup(x);
}
void modify(int x, int l, int r, int pos, int val) {
  if (l == r) {
    t[x] = Node(l, val);
    return;
  }
  pushdown(x);
  if (pos <= ((l + r) >> 1)) modify((x << 1), l, ((l + r) >> 1), pos, val);
  if (pos > ((l + r) >> 1))
    modify((x << 1 | 1), ((l + r) >> 1) + 1, r, pos, val);
  pushup(x);
}
void UpdateRev(int x, int l, int r, int L, int R) {
  if (L > r || R < l) return;
  if (L <= l && r <= R) {
    reverse(x);
    rev[x] ^= 1;
    return;
  }
  pushdown(x);
  UpdateRev((x << 1), l, ((l + r) >> 1), L, R);
  UpdateRev((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
  pushup(x);
}
Node query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return t[x];
  pushdown(x);
  if (R <= ((l + r) >> 1)) return query((x << 1), l, ((l + r) >> 1), L, R);
  if (L > ((l + r) >> 1))
    return query((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
  return query((x << 1), l, ((l + r) >> 1), L, R) +
         query((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
}
inline void init(void) {
  n = fread();
  for (int i = 1; i <= n; ++i) a[i] = fread();
  build(1, 1, n);
}
queue<pair<int, int> > q;
int Answer(int l, int r, int k) {
  int ret = 0;
  Tuple now = query(1, 1, n, l, r).maxw;
  while (now.val > 0 && k) {
    ret += now.val;
    q.push(make_pair(now.l, now.r));
    UpdateRev(1, 1, n, now.l, now.r);
    --k;
    now = query(1, 1, n, l, r).maxw;
  }
  while (!q.empty())
    UpdateRev(1, 1, n, q.front().first, q.front().second), q.pop();
  return ret;
}
inline void work(void) {
  Q = fread();
  int opt, l, r, k, x, v;
  for (int q = 1; q <= Q; ++q) {
    opt = fread();
    if (opt == 0) {
      x = fread();
      v = fread();
      modify(1, 1, n, x, v);
    } else {
      l = fread(), r = fread(), k = fread();
      printf("%d\n", Answer(l, r, k));
    }
  }
}
int main() {
  init();
  work();
  return 0;
}
