#include <bits/stdc++.h>
using namespace std;
inline long long rd() {
  long long x = 0;
  int ch = getchar(), f = 1;
  while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void rt(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10)
    rt(x / 10), putchar(x % 10 + '0');
  else
    putchar(x + '0');
}
const int maxn = 400005;
int a[maxn];
struct node {
  int lf[2][2], rg[2][2], md[2][3], sum;
  bool rev;
} b[maxn];
node operator+(node a, node b) {
  node ret;
  node *x = &a, *y = &b, *t = &ret;
  t->rev = 0;
  t->sum = x->sum + y->sum;
  if (x->sum + y->lf[0][0] > x->lf[0][0])
    t->lf[0][0] = x->sum + y->lf[0][0], t->lf[0][1] = y->lf[0][1];
  else
    t->lf[0][0] = x->lf[0][0], t->lf[0][1] = x->lf[0][1];
  if (x->sum + y->lf[1][0] < x->lf[1][0])
    t->lf[1][0] = x->sum + y->lf[1][0], t->lf[1][1] = y->lf[1][1];
  else
    t->lf[1][0] = x->lf[1][0], t->lf[1][1] = x->lf[1][1];
  if (y->sum + x->rg[0][0] > y->rg[0][0])
    t->rg[0][0] = y->sum + x->rg[0][0], t->rg[0][1] = x->rg[0][1];
  else
    t->rg[0][0] = y->rg[0][0], t->rg[0][1] = y->rg[0][1];
  if (y->sum + x->rg[1][0] < y->rg[1][0])
    t->rg[1][0] = y->sum + x->rg[1][0], t->rg[1][1] = x->rg[1][1];
  else
    t->rg[1][0] = y->rg[1][0], t->rg[1][1] = y->rg[1][1];
  t->md[0][0] = x->md[0][0], t->md[0][1] = x->md[0][1],
  t->md[0][2] = x->md[0][2];
  if (y->md[0][0] > t->md[0][0])
    t->md[0][0] = y->md[0][0], t->md[0][1] = y->md[0][1],
    t->md[0][2] = y->md[0][2];
  if (x->rg[0][0] + y->lf[0][0] > t->md[0][0])
    t->md[0][0] = x->rg[0][0] + y->lf[0][0], t->md[0][1] = x->rg[0][1],
    t->md[0][2] = y->lf[0][1];
  t->md[1][0] = x->md[1][0], t->md[1][1] = x->md[1][1],
  t->md[1][2] = x->md[1][2];
  if (y->md[1][0] < t->md[1][0])
    t->md[1][0] = y->md[1][0], t->md[1][1] = y->md[1][1],
    t->md[1][2] = y->md[1][2];
  if (x->rg[1][0] + y->lf[1][0] < t->md[1][0])
    t->md[1][0] = x->rg[1][0] + y->lf[1][0], t->md[1][1] = x->rg[1][1],
    t->md[1][2] = y->lf[1][1];
  return ret;
}
void update(int i) { b[i] = b[(i << 1)] + b[(i << 1 | 1)]; }
void R(int i) {
  node *t = b + i;
  t->sum = -t->sum;
  swap(t->lf[0][0], t->lf[1][0]), swap(t->lf[0][1], t->lf[1][1]);
  t->lf[0][0] = -t->lf[0][0], t->lf[1][0] = -t->lf[1][0];
  swap(t->rg[0][0], t->rg[1][0]), swap(t->rg[0][1], t->rg[1][1]);
  t->rg[0][0] = -t->rg[0][0], t->rg[1][0] = -t->rg[1][0];
  swap(t->md[0][0], t->md[1][0]), swap(t->md[0][1], t->md[1][1]),
      swap(t->md[0][2], t->md[1][2]);
  t->md[0][0] = -t->md[0][0], t->md[1][0] = -t->md[1][0];
}
void pushdown(int i) {
  if (b[i].rev) {
    R((i << 1)), R((i << 1 | 1));
    b[(i << 1)].rev ^= 1, b[(i << 1 | 1)].rev ^= 1;
    b[i].rev = 0;
  }
}
void build(int i, int l, int r) {
  node *x = b + i;
  if (l == r) {
    x->sum = x->lf[0][0] = x->rg[0][0] = x->md[0][0] = x->lf[1][0] =
        x->rg[1][0] = x->md[1][0] = a[l];
    x->lf[0][1] = x->lf[1][1] = x->rg[0][1] = x->rg[1][1] = x->md[0][1] =
        x->md[0][2] = x->md[1][1] = x->md[1][2] = l;
    return;
  }
  int mid = l + r >> 1;
  build((i << 1), l, mid), build((i << 1 | 1), mid + 1, r);
  update(i);
}
void modify(int i, int l, int r, int pos, int v) {
  node *x = b + i;
  if (l == r) {
    x->sum = x->lf[0][0] = x->rg[0][0] = x->md[0][0] = x->lf[1][0] =
        x->rg[1][0] = x->md[1][0] = v;
    return;
  }
  pushdown(i);
  int mid = l + r >> 1;
  if (pos <= mid)
    modify((i << 1), l, mid, pos, v);
  else
    modify((i << 1 | 1), mid + 1, r, pos, v);
  update(i);
}
node Q(int i, int l, int r, int fr, int bh) {
  if (l == fr && r == bh) return b[i];
  int mid = l + r >> 1;
  pushdown(i);
  if (bh <= mid)
    return Q((i << 1), l, mid, fr, bh);
  else if (fr > mid)
    return Q((i << 1 | 1), mid + 1, r, fr, bh);
  else
    return Q((i << 1), l, mid, fr, mid) +
           Q((i << 1 | 1), mid + 1, r, mid + 1, bh);
}
void rever(int i, int l, int r, int fr, int bh) {
  if (l == fr && r == bh) {
    R(i);
    b[i].rev ^= 1;
    return;
  }
  pushdown(i);
  int mid = l + r >> 1;
  if (bh <= mid)
    rever((i << 1), l, mid, fr, bh);
  else if (fr > mid)
    rever((i << 1 | 1), mid + 1, r, fr, bh);
  else
    rever((i << 1), l, mid, fr, mid),
        rever((i << 1 | 1), mid + 1, r, mid + 1, bh);
  update(i);
}
pair<int, int> xl[25];
int cs, n;
int main() {
  n = rd();
  for (int i = 1; i <= (int)n; i++) a[i] = rd();
  build(1, 1, n);
  for (int q = rd(); q--;) {
    int opt = rd();
    if (opt == 0) {
      int k = rd(), x = rd();
      modify(1, 1, n, k, x);
    } else {
      int l = rd(), r = rd(), k = rd(), ans = 0;
      cs = 0;
      for (int i = 1; i <= (int)k; i++) {
        node qry = Q(1, 1, n, l, r);
        if (qry.md[0][0] <= 0) break;
        ans += qry.md[0][0];
        if (i != k)
          xl[++cs] = make_pair(qry.md[0][1], qry.md[0][2]),
          rever(1, 1, n, qry.md[0][1], qry.md[0][2]);
      }
      for (int i = cs; i >= (int)1; i--)
        rever(1, 1, n, xl[i].first, xl[i].second);
      rt(ans), putchar('\n');
    }
  }
}
