#include <bits/stdc++.h>
template <int N, class Val, class Tag>
class SegTree {
 private:
  Val data[N << 1];
  Tag tag[N << 1];
  bool ht[N << 1];
  int size;
  int rl, rr;
  using MergeFn = std::function<Val(const Val&, const Val&)>;
  using ModifyFn = std::function<Val(const Val&, const Tag&, int)>;
  using TagMergeFn = std::function<Tag(const Tag&, const Tag&)>;
  MergeFn merge;
  ModifyFn modv;
  TagMergeFn mtag;
  void init_(int l, int r, int id, const Val& val) {
    if (r - l == 1) {
      data[id] = val;
      return;
    }
    int m = (l + r) >> 1;
    int ir = id + ((m - l) << 1);
    init_(l, m, id + 1, val);
    init_(m, r, ir, val);
    data[id] = merge(data[id + 1], data[ir]);
  }
  template <class RAIter>
  void init_(int l, int r, int id, RAIter first, RAIter last) {
    if (r - l == 1) {
      data[id] = *first;
      return;
    }
    int m = (l + r) >> 1;
    int ir = id + ((m - l) << 1);
    init_(l, m, id + 1, first, first + (m - l));
    init_(m, r, ir, first + (m - l), last);
    data[id] = merge(data[id + 1], data[ir]);
  }
  template <class RAIter, class Proj>
  void init_(int l, int r, int id, RAIter first, RAIter last, Proj proj) {
    if (r - l == 1) {
      data[id] = proj(*first);
      return;
    }
    int m = (l + r) >> 1;
    int ir = id + ((m - l) << 1);
    init_(l, m, id + 1, first, first + (m - l), proj);
    init_(m, r, ir, first + (m - l), last, proj);
    data[id] = merge(data[id + 1], data[ir]);
  }
  void push_aux_(int c, int p) {
    tag[c] = ht[c] ? mtag(tag[c], tag[p]) : tag[p];
    ht[c] = true;
  }
  void push_(int l, int r, int id) {
    if (!ht[id]) return;
    data[id] = modv(data[id], tag[id], r - l);
    if (r - l > 1) {
      int m = (l + r) >> 1;
      int ir = id + ((m - l) << 1);
      push_aux_(id + 1, id);
      push_aux_(ir, id);
    }
    ht[id] = false;
  }
  inline void set_(int id, const Tag& key) {
    tag[id] = key;
    ht[id] = true;
  }
  Val query_(int l, int r, int id) {
    while (!(rl <= l && rr >= r)) {
      int m = (l + r) >> 1;
      int ir = id + ((m - l) << 1);
      push_(l, m, id + 1);
      push_(m, r, ir);
      if (rr <= m) {
        r = m;
        id += 1;
      } else if (rl >= m) {
        l = m;
        id = ir;
      } else
        return merge(query_(l, m, id + 1), query_(m, r, ir));
    }
    return data[id];
  }
  void modify_(int l, int r, int id, const Tag& key) {
    push_(l, r, id);
    if (rl <= l && rr >= r) {
      set_(id, key);
      push_(l, r, id);
    } else if (!(rr <= l || rl >= r)) {
      int m = (l + r) >> 1;
      int ir = id + ((m - l) << 1);
      modify_(l, m, id + 1, key);
      modify_(m, r, ir, key);
      data[id] = merge(data[id + 1], data[ir]);
    }
  }

 public:
  void init(int s, const Val& val, MergeFn mef, ModifyFn mof, TagMergeFn tmf) {
    size = s;
    merge = mef;
    modv = mof;
    mtag = tmf;
    memset(ht, 0, sizeof(ht));
    init_(0, size, 0, val);
  }
  template <class RAIter>
  void init(RAIter first, RAIter last, MergeFn mef, ModifyFn mof,
            TagMergeFn tmf) {
    size = last - first;
    merge = mef;
    modv = mof;
    mtag = tmf;
    memset(ht, 0, sizeof(ht));
    init_(0, size, 0, first, last);
  }
  template <class RAIter, class Proj>
  void init(RAIter first, RAIter last, Proj proj, MergeFn mef, ModifyFn mof,
            TagMergeFn tmf) {
    size = last - first;
    merge = mef;
    modv = mof;
    mtag = tmf;
    memset(ht, 0, sizeof(ht));
    init_(0, size, 0, first, last, proj);
  }
  Val query(int left, int right) {
    rl = left;
    rr = right;
    push_(0, size, 0);
    return query_(0, size, 0);
  }
  Val query(int pos) {
    int l = 0, r = size, id = 0;
    while (1) {
      push_(l, r, id);
      if (r - l == 1) return data[id];
      int m = (l + r) >> 1;
      int ir = id + ((m - l) << 1);
      if (pos < m) {
        id += 1;
        r = m;
      } else {
        id = ir;
        l = m;
      }
    }
  }
  void modify(int left, int right, const Tag& key) {
    rl = left;
    rr = right;
    modify_(0, size, 0, key);
  }
  void modify(int pos, const Tag& key) {
    rl = pos;
    rr = pos + 1;
    modify_(0, size, 0, key);
  }
};
struct Range {
  int left, right, val;
  bool operator<(const Range& rhs) const { return val < rhs.val; }
  Range operator+(const Range& rhs) const {
    if (right != rhs.left) throw std::logic_error("Cannot merge!");
    return {left, rhs.right, val + rhs.val};
  }
  Range operator-() const { return {left, right, -val}; }
};
struct Node {
  Range leftMin, leftMax;
  Range rightMin, rightMax;
  Range optMin, optMax;
  Range sum;
};
struct Tag {
  int type;
  int pos, key;
};
auto merge = [](const Node& lhs, const Node& rhs) -> Node {
  return {std::min(lhs.leftMin, lhs.sum + rhs.leftMin),
          std::max(lhs.leftMax, lhs.sum + rhs.leftMax),
          std::min(rhs.rightMin, lhs.rightMin + rhs.sum),
          std::max(rhs.rightMax, lhs.rightMax + rhs.sum),
          std::min({lhs.optMin, rhs.optMin, lhs.rightMin + rhs.leftMin}),
          std::max({lhs.optMax, rhs.optMax, lhs.rightMax + rhs.leftMax}),
          lhs.sum + rhs.sum};
};
auto modify = [](const Node& x, const Tag& tag, int len) -> Node {
  if (tag.type == 0)
    return {{tag.pos, tag.pos + 1, tag.key},
            {tag.pos, tag.pos + 1, tag.key},
            {tag.pos, tag.pos + 1, tag.key},
            {tag.pos, tag.pos + 1, tag.key},
            {tag.pos, tag.pos + 1, std::min(tag.key, 0)},
            {tag.pos, tag.pos + 1, std::max(tag.key, 0)},
            {tag.pos, tag.pos + 1, tag.key}};
  else if (tag.type == 1)
    return {-x.leftMax, -x.leftMin, -x.rightMax, -x.rightMin,
            -x.optMax,  -x.optMin,  -x.sum};
  else
    return x;
};
auto mergeTag = [](const Tag& orig, const Tag& cur) -> Tag {
  if (orig.type == cur.type) return {2, 0, 0};
  return {1, 0, 0};
};
const int maxN = (int)1e5 + 10;
int N, Q, A[maxN];
void input() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) scanf("%d", A + i);
  scanf("%d", &Q);
}
SegTree<maxN, Node, Tag> seg;
auto proj = [](int val) -> Node {
  static int l = -1;
  l += 1;
  return {{l, l + 1, val},
          {l, l + 1, val},
          {l, l + 1, val},
          {l, l + 1, val},
          {l, l + 1, std::min(val, 0)},
          {l, l + 1, std::max(val, 0)},
          {l, l + 1, val}};
};
void solve() {
  seg.init(A + 1, A + N + 1, proj, merge, modify, mergeTag);
  int cmd;
  int p, val, l, r, k;
  std::stack<int> sl, sr;
  while (Q--) {
    scanf("%d", &cmd);
    if (cmd == 0) {
      scanf("%d%d", &p, &val);
      seg.modify(p - 1, {0, p - 1, val});
    } else if (cmd == 1) {
      scanf("%d%d%d", &l, &r, &k);
      int ans = 0;
      for (; k > 0; k--) {
        auto cur = seg.query(l - 1, r).optMax;
        if (cur.val <= 0) break;
        ans += cur.val;
        seg.modify(cur.left, cur.right, {1, 0, 0});
        sl.push(cur.left);
        sr.push(cur.right);
      }
      printf("%d\n", ans);
      while (!sl.empty()) {
        seg.modify(sl.top(), sr.top(), {1, 0, 0});
        sl.pop();
        sr.pop();
      }
    }
  }
}
int main() {
  input();
  solve();
  return 0;
}
