#include <bits/stdc++.h>
using namespace std;
int rd() { return RAND_MAX == 32767 ? ((rand() << 15) ^ rand()) : rand(); }
const int maxn = 100010;
int a[maxn];
struct Segment {
  int l, r, sum;
  Segment() {}
  Segment(int l_, int r_, int sum_) : l(l_), r(r_), sum(sum_) {}
  Segment operator+(const Segment &o) const {
    Segment res;
    res.sum = sum + o.sum;
    res.l = l;
    res.r = o.r;
    return res;
  }
  bool operator<(const Segment &o) const { return sum < o.sum; }
} cntR, cntS;
struct Tree {
  int l, r, chg;
  Segment sum, maxL, maxR, maxS, minL, minR, minS;
  Tree *lc, *rc;
  void setNode(int val) {
    sum = Segment(l, r, val);
    if (val > 0)
      maxL = maxR = maxS = Segment(l, r, val);
    else {
      maxL = maxS = Segment(l, l, 0);
      maxR = Segment(r, r, 0);
    }
    if (val < 0)
      minL = minR = minS = Segment(l, r, val);
    else {
      minL = minS = Segment(l, l, 0);
      minR = Segment(r, r, 0);
    }
  }
  Tree(int l_, int r_) : l(l_), r(r_) {
    lc = l + 1 < r ? new Tree(l, (l + r) >> 1) : NULL;
    rc = l + 1 < r ? new Tree((l + r) >> 1, r) : NULL;
    chg = 0;
    if (l + 1 < r)
      fresh();
    else
      setNode(a[l]);
  }
  void fresh() {
    maxS = max(max(lc->maxS, rc->maxS), lc->maxR + rc->maxL);
    maxL = max(lc->maxL, lc->sum + rc->maxL);
    maxR = max(rc->maxR, lc->maxR + rc->sum);
    minS = min(min(lc->minS, rc->minS), lc->minR + rc->minL);
    minL = min(lc->minL, lc->sum + rc->minL);
    minR = min(rc->minR, lc->minR + rc->sum);
    sum = lc->sum + rc->sum;
  }
  void modify() {
    chg ^= 1;
    swap(minL, maxL);
    swap(minR, maxR);
    swap(minS, maxS);
    maxL.sum = -maxL.sum;
    maxR.sum = -maxR.sum;
    maxS.sum = -maxS.sum;
    minL.sum = -minL.sum;
    minR.sum = -minR.sum;
    minS.sum = -minS.sum;
    sum.sum = -sum.sum;
  }
  void down() {
    chg = 0;
    lc->modify();
    rc->modify();
  }
  void change(int x, int y) {
    if (l + 1 == r)
      setNode(y);
    else {
      if (chg) down();
      x < (l + r) >> 1 ? lc->change(x, y) : rc->change(x, y);
      fresh();
    }
  }
  void query(int ll, int rr) {
    if (ll <= l && rr >= r) {
      cntS = max(max(cntS, maxS), cntR + maxL);
      cntR = max(maxR, cntR + sum);
    } else {
      if (chg) down();
      if (ll < (l + r) >> 1) lc->query(ll, rr);
      if (rr > (l + r) >> 1) rc->query(ll, rr);
      fresh();
    }
  }
  void negative(int ll, int rr) {
    if (ll <= l && rr >= r)
      modify();
    else {
      if (chg) down();
      if (ll < (l + r) >> 1) lc->negative(ll, rr);
      if (rr > (l + r) >> 1) rc->negative(ll, rr);
      fresh();
    }
  }
} * root;
int main() {
  int n, m;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  root = new Tree(0, n);
  cin >> m;
  for (int i = 0; i < m; i++) {
    int opt;
    cin >> opt;
    if (opt == 0) {
      int pos, val;
      cin >> pos >> val;
      pos--;
      root->change(pos, val);
    } else {
      int l, r, k, res = 0;
      cin >> l >> r >> k;
      l--;
      vector<pair<int, int> > b;
      for (int i = 0; i < k; i++) {
        cntS = cntR = Segment(l, l, 0);
        root->query(l, r);
        res += cntS.sum;
        if (cntS.l < cntS.r) {
          root->negative(cntS.l, cntS.r);
          b.push_back(make_pair(cntS.l, cntS.r));
        } else
          break;
      }
      for (int i = 0; i < b.size(); i++)
        root->negative(b[i].first, b[i].second);
      cout << res << endl;
    }
  }
  return 0;
}
