#include <bits/stdc++.h>
using namespace std;
long long inf = 10000000000000000LL;
int n, m, a[100005];
vector<pair<int, int>> q;
struct data {
  int maxl, maxr, maxs, sum, lp, rp, p1, p2;
  inline void init(int k, int d) {
    lp = rp = p1 = p2 = k;
    maxl = maxr = maxs = sum = d;
  }
};
struct node {
  int l, r;
  bool tag;
  data mins, maxs;
  inline void init(int d) {
    mins.init(l, -d);
    maxs.init(l, d);
  }
} t[400005];
inline void pushdown(int k) {
  if (t[k].l == t[k].r) return;
  if (t[k].tag) {
    swap(t[((k) << 1)].mins, t[((k) << 1)].maxs);
    swap(t[(((k) << 1) + 1)].mins, t[(((k) << 1) + 1)].maxs);
    t[((k) << 1)].tag ^= 1;
    t[(((k) << 1) + 1)].tag ^= 1;
    t[k].tag ^= 1;
  }
}
inline data merge(data a, data b) {
  data t;
  t.sum = a.sum + b.sum;
  t.maxl = a.maxl;
  t.lp = a.lp;
  if (a.sum + b.maxl > t.maxl) t.maxl = a.sum + b.maxl, t.lp = b.lp;
  t.maxr = b.maxr;
  t.rp = b.rp;
  if (b.sum + a.maxr > t.maxr) t.maxr = b.sum + a.maxr, t.rp = a.rp;
  t.maxs = a.maxr + b.maxl;
  t.p1 = a.rp;
  t.p2 = b.lp;
  if (t.maxs < a.maxs) t.maxs = a.maxs, t.p1 = a.p1, t.p2 = a.p2;
  if (t.maxs < b.maxs) t.maxs = b.maxs, t.p1 = b.p1, t.p2 = b.p2;
  return t;
}
inline void update(int k) {
  t[k].mins = merge(t[((k) << 1)].mins, t[(((k) << 1) + 1)].mins);
  t[k].maxs = merge(t[((k) << 1)].maxs, t[(((k) << 1) + 1)].maxs);
}
inline void build(int k, int l, int r) {
  t[k].l = l;
  t[k].r = r;
  if (l == r) {
    t[k].init(a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(((k) << 1), l, mid);
  build((((k) << 1) + 1), mid + 1, r);
  update(k);
}
inline void reverse(int k, int x, int y) {
  pushdown(k);
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (l == x && y == r) {
    swap(t[k].mins, t[k].maxs);
    t[k].tag ^= 1;
    return;
  }
  if (y <= mid)
    reverse(((k) << 1), x, y);
  else if (x > mid)
    reverse((((k) << 1) + 1), x, y);
  else
    reverse(((k) << 1), x, mid), reverse((((k) << 1) + 1), mid + 1, y);
  update(k);
}
inline data query(int k, int x, int y) {
  pushdown(k);
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (l == x && y == r) return t[k].maxs;
  if (y <= mid) return query(((k) << 1), x, y);
  if (x > mid) return query((((k) << 1) + 1), x, y);
  return merge(query(((k) << 1), x, mid), query((((k) << 1) + 1), mid + 1, y));
}
inline void solve(int l, int r, int k) {
  int ans = 0;
  q.clear();
  for (int i = 1; i <= k; i++) {
    data t = query(1, l, r);
    if (t.maxs > 0)
      ans += t.maxs;
    else
      break;
    reverse(1, t.p1, t.p2);
    q.push_back(make_pair(t.p1, t.p2));
  }
  for (int i = q.size() - 1; i >= 0; i--) reverse(1, q[i].first, q[i].second);
  printf("%d\n", ans);
}
inline void change(int k, int pos, int val) {
  pushdown(k);
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (l == r) {
    t[k].init(val);
    return;
  }
  if (pos <= mid)
    change(((k) << 1), pos, val);
  else
    change((((k) << 1) + 1), pos, val);
  update(k);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    int op, l, r, k;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      scanf("%d", &k);
      solve(l, r, k);
    } else
      change(1, l, r);
  }
  return 0;
}
