#include <bits/stdc++.h>
using namespace std;
int n, a[100010], m;
struct data {
  int lx, rx, mx, sum, pl, pr, p1, p2;
  inline void init(int pos, int x) {
    pl = pr = p1 = p2 = pos, lx = rx = mx = sum = x;
  }
};
struct Tree {
  bool tmp;
  data mx, mn;
  inline void init(int pos, int x) { mx.init(pos, x), mn.init(pos, -x); }
} t[262150];
inline data merge(data ls, data rs) {
  data res;
  res.sum = ls.sum + rs.sum;
  res.lx = ls.sum + rs.lx > ls.lx ? ls.sum + rs.lx : ls.lx;
  res.pl = ls.sum + rs.lx > ls.lx ? rs.pl : ls.pl;
  res.rx = rs.sum + ls.rx > rs.rx ? rs.sum + ls.rx : rs.rx;
  res.pr = rs.sum + ls.rx > rs.rx ? ls.pr : rs.pr;
  res.mx = ls.rx + rs.lx, res.p1 = ls.pr, res.p2 = rs.pl;
  if (res.mx < ls.mx) res.mx = ls.mx, res.p1 = ls.p1, res.p2 = ls.p2;
  if (res.mx < rs.mx) res.mx = rs.mx, res.p1 = rs.p1, res.p2 = rs.p2;
  return res;
}
inline void update(int p) {
  t[p].mx = merge(t[p << 1].mx, t[p << 1 | 1].mx);
  t[p].mn = merge(t[p << 1].mn, t[p << 1 | 1].mn);
}
inline void build_tree(int p, int l, int r) {
  if (l == r) {
    t[p].init(l, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build_tree(p << 1, l, mid);
  build_tree(p << 1 | 1, mid + 1, r);
  update(p);
}
inline void push_down(int p) {
  if (t[p].tmp) {
    swap(t[p << 1].mx, t[p << 1].mn), t[p << 1].tmp ^= 1;
    swap(t[p << 1 | 1].mx, t[p << 1 | 1].mn), t[p << 1 | 1].tmp ^= 1;
    t[p].tmp = 0;
  }
}
inline data query(int p, int l, int r, int ll, int rr) {
  if (l >= ll && r <= rr) return t[p].mx;
  push_down(p);
  int mid = (l + r) >> 1;
  if (rr <= mid) return query(p << 1, l, mid, ll, rr);
  if (ll > mid) return query(p << 1 | 1, mid + 1, r, ll, rr);
  return merge(query(p << 1, l, mid, ll, rr),
               query(p << 1 | 1, mid + 1, r, ll, rr));
}
inline void rev(int p, int l, int r, int ll, int rr) {
  if (l >= ll && r <= rr) {
    swap(t[p].mx, t[p].mn), t[p].tmp ^= 1;
    return;
  }
  push_down(p);
  int mid = (l + r) >> 1;
  if (ll <= mid) rev(p << 1, l, mid, ll, rr);
  if (rr > mid) rev(p << 1 | 1, mid + 1, r, ll, rr);
  update(p);
}
pair<int, int> s[25];
int top;
inline void solve(int l, int r, int k) {
  int ans = 0;
  while (k--) {
    data tmp = query(1, 1, n, l, r);
    if (tmp.mx > 0)
      ans += tmp.mx;
    else
      break;
    rev(1, 1, n, tmp.p1, tmp.p2);
    s[++top] = make_pair(tmp.p1, tmp.p2);
  }
  while (top) rev(1, 1, n, s[top].first, s[top].second), top--;
  printf("%d\n", ans);
}
inline void modify(int p, int l, int r, int pos, int x) {
  if (l == r) {
    t[p].init(pos, x);
    return;
  }
  push_down(p);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(p << 1, l, mid, pos, x);
  else
    modify(p << 1 | 1, mid + 1, r, pos, x);
  update(p);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build_tree(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    int tp;
    scanf("%d", &tp);
    if (tp) {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      solve(l, r, k);
    } else {
      int pos, x;
      scanf("%d%d", &pos, &x);
      modify(1, 1, n, pos, x);
    }
  }
  return 0;
}
