#include <bits/stdc++.h>
int n, m, k, op, i, x, y, a[262142], t, l[262142], r[262142];
long long ans;
struct P {
  int vl, vr, vm, s, pl, pr, l, r;
  P() {}
  P(int x, long long v) { pl = pr = l = r = x, vl = vr = vm = s = v; }
  inline P operator+(P b) {
    P c;
    c.s = s + b.s;
    c.vl = vl, c.pl = pl;
    if (s + b.vl > c.vl) c.vl = s + b.vl, c.pl = b.pl;
    c.vr = b.vr, c.pr = b.pr;
    if (vr + b.s > c.vr) c.vr = vr + b.s, c.pr = pr;
    c.vm = vr + b.vl, c.l = pr, c.r = b.pl;
    if (vm > c.vm) c.vm = vm, c.l = l, c.r = r;
    if (b.vm > c.vm) c.vm = b.vm, c.l = b.l, c.r = b.r;
    return c;
  }
} tmp, all;
struct Q {
  P mi, ma;
  bool tag;
} T[262142];
inline void read(int& a) {
  char c;
  bool f = 0;
  a = 0;
  while (!((((c = getchar()) >= '0') && (c <= '9')) || (c == '-')))
    ;
  if (c != '-')
    a = c - '0';
  else
    f = 1;
  while (((c = getchar()) >= '0') && (c <= '9')) (a *= 10) += c - '0';
  if (f) a = -a;
}
inline void rev1(int x) {
  tmp = T[x].mi, T[x].mi = T[x].ma, T[x].ma = tmp, T[x].tag ^= 1;
}
inline void pb(int x) {
  if (T[x].tag) T[x].tag = 0, rev1(x << 1), rev1(x << 1 | 1);
}
inline void up(int x) {
  T[x].mi = T[x << 1].mi + T[x << 1 | 1].mi,
  T[x].ma = T[x << 1].ma + T[x << 1 | 1].ma;
}
void build(int x, int a, int b) {
  if (a == b) {
    T[x].mi = P(a, -::a[a]), T[x].ma = P(a, ::a[a]);
    return;
  }
  int mid = (a + b) >> 1;
  build(x << 1, a, mid), build(x << 1 | 1, mid + 1, b), up(x);
}
void change(int x, int a, int b, int c, int p) {
  if (a == b) {
    T[x].mi = P(a, -p), T[x].ma = P(a, p);
    return;
  }
  pb(x);
  int mid = (a + b) >> 1;
  if (c <= mid)
    change(x << 1, a, mid, c, p);
  else
    change(x << 1 | 1, mid + 1, b, c, p);
  up(x);
}
void rev(int x, int a, int b, int c, int d) {
  if (c <= a && b <= d) {
    rev1(x);
    return;
  }
  pb(x);
  int mid = (a + b) >> 1;
  if (c <= mid) rev(x << 1, a, mid, c, d);
  if (d > mid) rev(x << 1 | 1, mid + 1, b, c, d);
  up(x);
}
P ask(int x, int a, int b, int c, int d) {
  if (c <= a && b <= d) return T[x].ma;
  pb(x);
  int mid = (a + b) >> 1;
  P t;
  if (d <= mid)
    t = ask(x << 1, a, mid, c, d);
  else if (c > mid)
    t = ask(x << 1 | 1, mid + 1, b, c, d);
  else
    t = ask(x << 1, a, mid, c, d) + ask(x << 1 | 1, mid + 1, b, c, d);
  return up(x), t;
}
int main() {
  for (read(n), i = 1; i <= n; i++) read(a[i]);
  build(1, 1, n);
  read(m);
  while (m--) {
    read(op), read(x), read(y);
    if (op == 1) {
      read(k), ans = t = 0;
      while (k--) {
        all = ask(1, 1, n, x, y);
        if (all.vm > 0)
          ans += all.vm, rev(1, 1, n, all.l, all.r);
        else
          break;
        l[++t] = all.l, r[t] = all.r;
      }
      printf("%lld\n", ans);
      while (t) rev(1, 1, n, l[t], r[t]), t--;
    } else
      change(1, 1, n, x, y);
  }
  return 0;
}
