#include <bits/stdc++.h>
struct ios {
  template <typename ATP>
  inline ios &operator>>(ATP &x) {
    x = 0;
    int f = 1;
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
      if (c == '-') f = -1;
    while (c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
    x *= f;
    return *this;
  }
} io;
using namespace std;
template <typename ATP>
inline ATP Max(ATP a, ATP b) {
  return a > b ? a : b;
}
template <typename ATP>
inline ATP Min(ATP a, ATP b) {
  return a < b ? a : b;
}
template <typename ATP>
inline ATP Abs(ATP a) {
  return a < 0 ? -a : a;
}
const int N = 1e5 + 7;
int n;
struct RPG {
  int l, r, sum;
  bool operator<(const RPG &com) const { return sum < com.sum; }
  RPG operator+(const RPG &b) const { return (RPG){l, b.r, sum + b.sum}; }
};
struct nod {
  RPG lmax, lmin, rmin, rmax, mx, mn, all;
  bool operator<(const nod &com) const { return mx.sum < com.mx.sum; }
} t[N << 2];
bool tag[N << 2];
inline void Newnode(int rt, int pos, int val) {
  t[rt].lmax = t[rt].lmin = t[rt].rmax = t[rt].rmin = t[rt].mx = t[rt].mn =
      t[rt].all = (RPG){pos, pos, val};
}
inline nod Merge(nod x, nod y) {
  nod s;
  s.lmax = max(x.lmax, x.all + y.lmax);
  s.lmin = min(x.lmin, x.all + y.lmin);
  s.rmax = max(y.rmax, x.rmax + y.all);
  s.rmin = min(y.rmin, x.rmin + y.all);
  s.mx = max(max(x.mx, y.mx), x.rmax + y.lmax);
  s.mn = min(min(x.mn, y.mn), x.rmin + y.lmin);
  s.all = x.all + y.all;
  return s;
}
inline void Pushup(int &rt) { t[rt] = Merge(t[rt << 1], t[rt << 1 | 1]); }
inline void Pushrev(int rt) {
  swap(t[rt].lmax, t[rt].lmin);
  swap(t[rt].rmax, t[rt].rmin);
  swap(t[rt].mx, t[rt].mn);
  t[rt].lmax.sum = -t[rt].lmax.sum;
  t[rt].lmin.sum = -t[rt].lmin.sum;
  t[rt].rmax.sum = -t[rt].rmax.sum;
  t[rt].rmin.sum = -t[rt].rmin.sum;
  t[rt].mx.sum = -t[rt].mx.sum;
  t[rt].mn.sum = -t[rt].mn.sum;
  t[rt].all.sum = -t[rt].all.sum;
  tag[rt] ^= 1;
}
inline void Pushdown(int rt) {
  if (!tag[rt]) return;
  Pushrev(rt << 1);
  Pushrev(rt << 1 | 1);
  tag[rt] = 0;
}
inline void Modify(int rt, int l, int r, int x, int w) {
  if (l == r) {
    Newnode(rt, x, w);
    return;
  }
  Pushdown(rt);
  int mid = (l + r) >> 1;
  if (x <= mid)
    Modify(rt << 1, l, mid, x, w);
  else
    Modify(rt << 1 | 1, mid + 1, r, x, w);
  Pushup(rt);
}
inline void Updata(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    Pushrev(rt);
    return;
  }
  Pushdown(rt);
  int mid = (l + r) >> 1;
  if (L <= mid) Updata(rt << 1, l, mid, L, R);
  if (R > mid) Updata(rt << 1 | 1, mid + 1, r, L, R);
  Pushup(rt);
  return;
}
inline nod Query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) return t[rt];
  Pushdown(rt);
  int mid = (l + r) >> 1;
  if (R <= mid)
    return Query(rt << 1, l, mid, L, R);
  else if (L > mid)
    return Query(rt << 1 | 1, mid + 1, r, L, R);
  else
    return Merge(Query(rt << 1, l, mid, L, R),
                 Query(rt << 1 | 1, mid + 1, r, L, R));
  Pushup(rt);
}
nod sta[N];
int top;
inline int Solve(int l, int r, int K) {
  int ans = 0;
  while (K--) {
    nod s = Query(1, 1, n, l, r);
    if (s.mx.sum < 0) break;
    ans += s.mx.sum;
    Updata(1, 1, n, s.mx.l, s.mx.r);
    sta[++top] = s;
  }
  while (top) {
    nod s = sta[top--];
    Updata(1, 1, n, s.mx.l, s.mx.r);
  }
  return ans;
}
int main() {
  io >> n;
  for (register int i = (1); i <= (n); ++i) {
    int x;
    io >> x;
    Modify(1, 1, n, i, x);
  }
  int m;
  io >> m;
  while (m--) {
    int opt;
    io >> opt;
    if (opt) {
      int l, r, K;
      io >> l >> r >> K;
      printf("%d\n", Solve(l, r, K));
    } else {
      int x, w;
      io >> x >> w;
      Modify(1, 1, n, x, w);
    }
  }
  return 0;
}
