#include <bits/stdc++.h>
using namespace std;
const int INF = 1E9 + 7;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
struct MSS {
  pair<int, pair<int, int> > mss, left, right, sum;
  MSS(int x, int p) {
    sum = pair<int, pair<int, int> >(x, pair<int, int>(p, p));
    left = right = mss =
        (x > 0 ? pair<int, pair<int, int> >(x, pair<int, int>(p, p))
               : pair<int, pair<int, int> >(0, pair<int, int>(0, 0)));
  }
  MSS() { MSS(0, 0); }
  void out() {
    cout << "MSS sum " << sum.first << " l " << left.first << " r "
         << right.first << " mss " << mss.first << endl;
  }
};
inline pair<int, pair<int, int> > operator+(pair<int, pair<int, int> > a,
                                            pair<int, pair<int, int> > b) {
  if (a.second.first == 0) return b;
  if (b.second.first == 0) return a;
  return pair<int, pair<int, int> >(
      a.first + b.first, pair<int, int>(min(a.second.first, b.second.first),
                                        max(a.second.second, b.second.second)));
}
inline MSS join(MSS a, MSS b) {
  MSS r(0, 0);
  r.sum = a.sum + b.sum;
  r.left = max(a.left, a.sum + b.left);
  r.right = max(b.right, b.sum + a.right);
  r.mss = max(a.right + b.left, max(a.mss, b.mss));
  return r;
}
struct DP {
  MSS dp[2 * (1 << 17)][2];
  bool rev[2 * (1 << 17)];
  DP() {
    memset((dp), 0, sizeof(dp));
    memset((rev), 0, sizeof(rev));
  }
  inline void prepare(int x) {
    if (rev[x]) {
      swap(dp[x][0], dp[x][1]);
      if (x < (1 << 17)) {
        rev[x + x] ^= 1;
        rev[x + x + 1] ^= 1;
      }
      rev[x] = 0;
    }
  }
  inline void update(int x) {
    for (int i = 0; i < (2); ++i)
      dp[x][i] = join(dp[x + x][i], dp[x + x + 1][i]);
  }
  void set(int l, int r, int v, int x = 1, int ll = 1, int rr = (1 << 17)) {
    prepare(x);
    if (r < ll || rr < l) return;
    if (l <= ll && rr <= r) {
      dp[x][0] = MSS(v, l);
      dp[x][1] = MSS(-v, l);
    } else {
      set(l, r, v, x + x, ll, (ll + rr) / 2);
      set(l, r, v, x + x + 1, (ll + rr + 1) / 2, rr);
      update(x);
    }
  }
  MSS get(int l, int r, int x = 1, int ll = 1, int rr = (1 << 17)) {
    prepare(x);
    if (r < ll || rr < l) return MSS(0, 0);
    if (l <= ll && rr <= r) {
      return dp[x][0];
    } else {
      return join(get(l, r, x + x, ll, (ll + rr) / 2),
                  get(l, r, x + x + 1, (ll + rr + 1) / 2, rr));
    }
  }
  void swapy(int l, int r, int x = 1, int ll = 1, int rr = (1 << 17)) {
    prepare(x);
    if (r < ll || rr < l) return;
    if (l <= ll && rr <= r) {
      rev[x] ^= 1;
      prepare(x);
    } else {
      swapy(l, r, x + x, ll, (ll + rr) / 2);
      swapy(l, r, x + x + 1, (ll + rr + 1) / 2, rr);
      update(x);
    }
  }
  int get_ans(int l, int r, int k) {
    vector<pair<int, int> > swapped;
    int res = 0;
    for (int i = 0; i < (k); ++i) {
      pair<int, pair<int, int> > mss = get(l, r).mss;
      res += mss.first;
      if (mss.second.first != 0) {
        swapped.push_back(mss.second);
        swapy(mss.second.first, mss.second.second);
      }
    }
    for (__typeof((swapped).begin()) i = ((swapped).begin());
         i != (swapped).end(); ++i)
      swapy(i->first, i->second);
    return res;
  }
};
DP dp;
int n, m;
int main() {
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  cin >> n;
  for (int i = (1); i <= (n); ++i) {
    int x;
    cin >> x;
    dp.set(i, i, x);
  }
  cin >> m;
  while (m--) {
    int t;
    cin >> t;
    if (t == 0) {
      int i, val;
      cin >> i >> val;
      dp.set(i, i, val);
    } else {
      int l, r, k;
      cin >> l >> r >> k;
      cout << dp.get_ans(l, r, k) << endl;
    }
  }
  return 0;
}
