#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0;
  char ch = getchar(), w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * w;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
void setIO() {
  freopen("easy.in", "r", stdin);
  freopen("easy.out", "w", stdout);
}
const int N = 1e5 + 666;
int a[N], n;
struct Tp {
  int l, r, v;
  Tp() { l = r = v = 0; }
  Tp(int _v, int _l, int _r) { l = _l, r = _r, v = _v; }
  bool operator<(Tp b) const { return v < b.v; }
};
struct T {
  pair<int, int> mnl, mnr;
  pair<int, int> mxl, mxr;
  Tp mn, mx;
  int t;
  int s;
  int l, r;
  void init(int x, int v) {
    mn = Tp(v, x, x);
    mx = Tp(v, x, x);
    mnr = mnl = make_pair(v, x);
    mxl = mxr = make_pair(v, x);
    t = 0;
    s = v;
  }
  T() { t = 0; }
} t[N * 4];
T merge(T x, T y) {
  T res;
  res.s = 0;
  res.l = x.l;
  res.r = y.r;
  res.mn = min(x.mn, y.mn);
  res.mn =
      min(res.mn, Tp(x.mnr.first + y.mnl.first, x.mnr.second, y.mnl.second));
  res.mx = max(x.mx, y.mx);
  res.mx =
      max(res.mx, Tp(x.mxr.first + y.mxl.first, x.mxr.second, y.mxl.second));
  res.mxl = max(x.mxl, make_pair(x.s + y.mxl.first, y.mxl.second));
  res.mxr = max(y.mxr, make_pair(y.s + x.mxr.first, x.mxr.second));
  res.mnl = min(x.mnl, make_pair(x.s + y.mnl.first, y.mnl.second));
  res.mnr = min(y.mnr, make_pair(y.s + x.mnr.first, x.mnr.second));
  res.mx = max(res.mx, max(Tp(res.mxl.first, res.l, res.mxl.second),
                           Tp(res.mxr.first, res.mxr.second, res.r)));
  res.mn = min(res.mn, min(Tp(res.mnl.first, res.l, res.mnl.second),
                           Tp(res.mnr.first, res.mnr.second, res.r)));
  res.s = x.s + y.s;
  return res;
}
void build(int o, int l, int r) {
  t[o].l = l, t[o].r = r;
  t[o].t = 0;
  if (l == r) {
    t[o].init(l, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  if (l <= mid) build((o << 1), l, mid);
  if (r > mid) build((o << 1 | 1), mid + 1, r);
  t[o] = merge(t[(o << 1)], t[(o << 1 | 1)]);
}
void chg(T &x) {
  x.mn.v *= -1;
  x.mx.v *= -1;
  x.mnl.first *= -1;
  x.mxl.first *= -1;
  x.mnr.first *= -1;
  x.mxr.first *= -1;
  x.s *= -1;
  swap(x.mn, x.mx);
  swap(x.mnl, x.mxl);
  swap(x.mnr, x.mxr);
  x.t ^= 1;
}
void down(int o) {
  if (t[o].t) {
    chg(t[(o << 1)]);
    chg(t[(o << 1 | 1)]);
    t[o].t = 0;
  }
}
T query(int o, int l, int r) {
  if (t[o].l >= l && t[o].r <= r) {
    return t[o];
  }
  int mid = (t[o].l + t[o].r) >> 1;
  down(o);
  if (r <= mid) return query((o << 1), l, r);
  if (l > mid) return query((o << 1 | 1), l, r);
  T lt = query((o << 1), l, r);
  T rt = query((o << 1 | 1), l, r);
  return merge(lt, rt);
}
void ins1(int o, int l, int r) {
  if (l <= t[o].l && r >= t[o].r) {
    chg(t[o]);
    return;
  }
  int mid = (t[o].l + t[o].r) >> 1;
  down(o);
  if (l <= mid) ins1((o << 1), l, r);
  if (r > mid) ins1((o << 1 | 1), l, r);
  t[o] = merge(t[(o << 1)], t[(o << 1 | 1)]);
}
void ins2(int o, int x, int v) {
  if (t[o].l == t[o].r) {
    t[o].init(x, v);
    return;
  }
  int mid = (t[o].l + t[o].r) >> 1;
  down(o);
  if (x <= mid)
    ins2((o << 1), x, v);
  else
    ins2((o << 1 | 1), x, v);
  t[o] = merge(t[(o << 1)], t[(o << 1 | 1)]);
}
pair<int, int> tmp[77];
int cal(int l, int r, int k) {
  int res = 0, tot = 0, ans = 0;
  k = min(r - l + 1, k);
  for (int i = 1; i <= k; ++i) {
    T now = query(1, l, r);
    tmp[++tot] = make_pair(now.mx.l, now.mx.r);
    res += now.mx.v;
    ans = max(ans, res);
    ins1(1, now.mx.l, now.mx.r);
  }
  for (int i = tot; i; --i) ins1(1, tmp[i].first, tmp[i].second);
  return ans;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n);
  int Q = read();
  while (Q--) {
    int op = read();
    if (op == 1) {
      int l = read(), r = read(), k = read();
      writeln(cal(l, r, k));
    } else {
      int x = read(), v = read();
      ins2(1, x, v);
    }
  }
  return 0;
}
