#include <bits/stdc++.h>
using namespace std;
const int NN = 100005;
int n, m, ww, ee, a[NN];
bool qwe = false;
inline void read(int &x) {
  x = 0;
  char ch = getchar();
  bool f = false;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = true;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
struct segnode {
  int l, r, lmax, _lmax, lmin, _lmin, rmax, _rmax, rmin, _rmin, tmax, tmin, sum;
  pair<int, int> _tmax, _tmin;
  int tag;
  void out() {
    printf("tag=%d\n", tag);
    printf("  tag=%s\n", tag == 1 ? "true" : "false");
    printf("  tmax=%d   [%d,%d]\n", tmax, _tmax.first, _tmax.second);
    printf("  tmin=%d   [%d,%d]\n", tmin, _tmin.first, _tmin.second);
  }
  void clear() {
    lmax = rmax = tmax = -999999999;
    lmin = rmin = tmin = 999999999;
    sum = 0;
  }
  void set(int x) {
    sum = x * (r - l);
    if (x >= 0) {
      lmax = rmax = tmax = x * (r - l);
      _lmax = r - 1, _rmax = l, _tmax = make_pair(l, r - 1);
      lmin = rmin = tmin = 0;
      _lmin = l - 1, _rmin = r, _tmin = make_pair(l, l - 1);
    } else {
      lmax = rmax = tmax = 0;
      _lmax = l - 1, _rmax = r, _tmax = make_pair(l, l - 1);
      lmin = rmin = tmin = x * (r - l);
      _lmin = r - 1, _rmin = l, _tmin = make_pair(l, r - 1);
    }
  }
  void qufu() {
    tag ^= 1;
    sum = -sum;
    int t;
    t = lmax, lmax = -lmin, lmin = -t;
    t = _lmax, _lmax = _lmin, _lmin = t;
    t = rmax, rmax = -rmin, rmin = -t;
    t = _rmax, _rmax = _rmin, _rmin = t;
    t = tmax, tmax = -tmin, tmin = -t;
    swap(_tmax, _tmin);
  }
  friend segnode operator+(segnode a, segnode b) {
    segnode res;
    res.tag = 0;
    res.l = a.l, res.r = b.r;
    res.sum = a.sum + b.sum;
    if (a.lmax > a.sum + b.lmax)
      res.lmax = a.lmax, res._lmax = a._lmax;
    else
      res.lmax = a.sum + b.lmax, res._lmax = b._lmax;
    if (a.lmin < a.sum + b.lmin)
      res.lmin = a.lmin, res._lmin = a._lmin;
    else
      res.lmin = a.sum + b.lmin, res._lmin = b._lmin;
    if (b.rmax > b.sum + a.rmax)
      res.rmax = b.rmax, res._rmax = b._rmax;
    else
      res.rmax = b.sum + a.rmax, res._rmax = a._rmax;
    if (b.rmin < b.sum + a.rmin)
      res.rmin = b.rmin, res._rmin = b._rmin;
    else
      res.rmin = b.sum + a.rmin, res._rmin = a._rmin;
    if (a.tmax > b.tmax)
      res.tmax = a.tmax, res._tmax = a._tmax;
    else
      res.tmax = b.tmax, res._tmax = b._tmax;
    if (a.rmax + b.lmax > res.tmax)
      res.tmax = a.rmax + b.lmax, res._tmax = make_pair(a._rmax, b._lmax);
    if (a.tmin < b.tmin)
      res.tmin = a.tmin, res._tmin = a._tmin;
    else
      res.tmin = b.tmin, res._tmin = b._tmin;
    if (a.rmin + b.lmin < res.tmin)
      res.tmin = a.rmin + b.lmin, res._tmin = make_pair(a._rmin, b._lmin);
    return res;
  }
} t[NN * 4], res;
inline void gogogo() {}
void build(int v, int l, int r) {
  t[v].l = l, t[v].r = r, t[v].tag = 0;
  if (r - l == 1) {
    t[v].set(a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build((v << 1), l, mid);
  build((v << 1 | 1), mid, r);
  t[v] = t[(v << 1)] + t[(v << 1 | 1)];
}
inline void pushdown(int v) {
  if (t[v].tag == 0) return;
  t[v].tag = 0;
  t[(v << 1)].qufu(), t[(v << 1 | 1)].qufu();
}
void change0(int v, int l, int r) {
  if (ww <= l && r <= ee) {
    t[v].qufu();
    return;
  }
  pushdown(v);
  int mid = (l + r) >> 1;
  if (ww < mid) change0((v << 1), l, mid);
  if (ee > mid) change0((v << 1 | 1), mid, r);
  t[v] = t[(v << 1)] + t[(v << 1 | 1)];
  gogogo();
}
void change(int v, int l, int r, int i, int x) {
  if (r - l == 1) {
    t[v].set(x);
    return;
  }
  pushdown(v);
  int mid = (l + r) >> 1;
  if (i < mid)
    change((v << 1), l, mid, i, x);
  else
    change((v << 1 | 1), mid, r, i, x);
  t[v] = t[(v << 1)] + t[(v << 1 | 1)];
}
void find(int v, int l, int r) {
  if (ww <= l && r <= ee) {
    res = res + t[v];
    return;
  }
  pushdown(v);
  int mid = (l + r) >> 1;
  if (ww < mid) find((v << 1), l, mid);
  if (ee > mid) find((v << 1 | 1), mid, r);
}
int main() {
  read(n);
  int i, x, y, L, R, K;
  for (i = 1; i <= n; i++) read(a[i]);
  build(1, 1, n + 1);
  for (read(m); m; m--) {
    read(x);
    if (x == 1) {
      read(L), read(R), read(K);
      int ans = 0, top = 0;
      static pair<int, int> sta[NN];
      for (i = 1; i <= K; i++) {
        ww = L, ee = R + 1;
        res.clear();
        res.l = L, res.r = R;
        find(1, 1, n + 1);
        if (res._tmax.first > res._tmax.second) break;
        ans += res.tmax;
        sta[++top] = res._tmax;
        ww = res._tmax.first, ee = res._tmax.second + 1;
        change0(1, 1, n + 1);
      }
      printf("%d\n", ans);
      while (top) {
        ww = sta[top].first, ee = sta[top].second + 1;
        change0(1, 1, n + 1);
        top--;
      }
    } else {
      read(x), read(y);
      change(1, 1, n + 1, x, y);
    }
  }
  return 0;
}
