#include <bits/stdc++.h>
using namespace std;
const int N = 111111, M = 11111111;
long long MOD = 998244353, inv2 = (MOD + 1) / 2;
int INF = int(1e9);
long double eps = 1e-8;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
long double pi = acos(-1.0L);
struct node {
  int tag, sum, l_mx, l_mn, r_mx, r_mn, l_mx_r, l_mn_r, r_mx_l, r_mn_l, mx, mn,
      mx_l, mx_r, mn_l, mn_r;
} t[N << 2], c[22];
int a[N], n;
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
void init() {
  n = read();
  for (int i = (int)1; i <= (int)n; i++) a[i] = read();
}
void pushup(node &p, node L, node R) {
  p.sum = L.sum + R.sum;
  p.l_mx = L.l_mx, p.l_mx_r = L.l_mx_r;
  if (L.sum + R.l_mx > p.l_mx) {
    p.l_mx = L.sum + R.l_mx;
    p.l_mx_r = R.l_mx_r;
  }
  p.l_mn = L.l_mn, p.l_mn_r = L.l_mn_r;
  if (L.sum + R.l_mn < p.l_mn) {
    p.l_mn = L.sum + R.l_mn;
    p.l_mn_r = R.l_mn_r;
  }
  p.r_mx = R.r_mx, p.r_mx_l = R.r_mx_l;
  if (R.sum + L.r_mx > p.r_mx) {
    p.r_mx = R.sum + L.r_mx;
    p.r_mx_l = L.r_mx_l;
  }
  p.r_mn = R.r_mn, p.r_mn_l = R.r_mn_l;
  if (R.sum + L.r_mn < p.r_mn) {
    p.r_mn = R.sum + L.r_mn;
    p.r_mn_l = L.r_mn_l;
  }
  p.mx = L.mx;
  p.mx_l = L.mx_l;
  p.mx_r = L.mx_r;
  if (R.mx > p.mx) {
    p.mx = R.mx;
    p.mx_l = R.mx_l;
    p.mx_r = R.mx_r;
  }
  if (L.r_mx + R.l_mx > p.mx) {
    p.mx = L.r_mx + R.l_mx;
    p.mx_l = L.r_mx_l;
    p.mx_r = R.l_mx_r;
  }
  p.mn = L.mn;
  p.mn_l = L.mn_l;
  p.mn_r = L.mn_r;
  if (R.mn < p.mn) {
    p.mn = R.mn;
    p.mn_l = R.mn_l;
    p.mn_r = R.mn_r;
  }
  if (L.r_mn + R.l_mn < p.mn) {
    p.mn = L.r_mn + R.l_mn;
    p.mn_l = L.r_mn_l;
    p.mn_r = R.l_mn_r;
  }
}
void rev(int p) {
  node tmp = t[p];
  t[p].sum = -tmp.sum;
  t[p].l_mx = -tmp.l_mn;
  t[p].l_mx_r = tmp.l_mn_r;
  t[p].l_mn = -tmp.l_mx;
  t[p].l_mn_r = tmp.l_mx_r;
  t[p].r_mx = -tmp.r_mn;
  t[p].r_mx_l = tmp.r_mn_l;
  t[p].r_mn = -tmp.r_mx;
  t[p].r_mn_l = tmp.r_mx_l;
  t[p].mx = -tmp.mn;
  t[p].mx_l = tmp.mn_l;
  t[p].mx_r = tmp.mn_r;
  t[p].mn = -tmp.mx;
  t[p].mn_l = tmp.mx_l;
  t[p].mn_r = tmp.mx_r;
}
void pushdown(int p) {
  if (t[p].tag) {
    rev(p << 1);
    t[p << 1].tag ^= 1;
    rev(p << 1 | 1);
    t[p << 1 | 1].tag ^= 1;
    t[p].tag = 0;
  }
}
void build(int l, int r, int p) {
  if (l == r) {
    t[p].tag = 0;
    t[p].sum = a[l];
    if (a[l] >= 0) {
      t[p].l_mx = a[l], t[p].l_mx_r = l;
      t[p].r_mx = a[l], t[p].r_mx_l = l;
      t[p].mx = a[l], t[p].mx_l = t[p].mx_r = l;
      t[p].l_mn = a[l], t[p].l_mn_r = l;
      t[p].r_mn = a[l], t[p].r_mn_l = l;
      t[p].mn = 0, t[p].mn_l = t[p].mn_r = 0;
    } else {
      t[p].l_mx = a[l], t[p].l_mx_r = l;
      t[p].r_mx = a[l], t[p].r_mx_l = l;
      t[p].mx = 0, t[p].mx_l = t[p].mx_r = 0;
      t[p].l_mn = a[l], t[p].l_mn_r = l;
      t[p].r_mn = a[l], t[p].r_mn_l = l;
      t[p].mn = a[l], t[p].mn_l = t[p].mn_r = l;
    }
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, p << 1);
  build(mid + 1, r, p << 1 | 1);
  pushup(t[p], t[p << 1], t[p << 1 | 1]);
}
void update(int l, int r, int x, int y, int p) {
  if (l == r) {
    t[p].sum = y;
    if (y >= 0) {
      t[p].l_mx = y, t[p].l_mx_r = l;
      t[p].r_mx = y, t[p].r_mx_l = l;
      t[p].mx = y, t[p].mx_l = t[p].mx_r = l;
      t[p].l_mn = y, t[p].l_mn_r = l;
      t[p].r_mn = y, t[p].r_mn_l = l;
      t[p].mn = 0, t[p].mn_l = t[p].mn_r = 0;
    } else {
      t[p].l_mx = y, t[p].l_mx_r = l;
      t[p].r_mx = y, t[p].r_mx_l = l;
      t[p].mx = 0, t[p].mx_l = t[p].mx_r = 0;
      t[p].l_mn = y, t[p].l_mn_r = l;
      t[p].r_mn = y, t[p].r_mn_l = l;
      t[p].mn = y, t[p].mn_l = t[p].mn_r = l;
    }
    return;
  }
  pushdown(p);
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(l, mid, x, y, p << 1);
  else
    update(mid + 1, r, x, y, p << 1 | 1);
  pushup(t[p], t[p << 1], t[p << 1 | 1]);
}
node query(int l, int r, int x, int y, int p) {
  if (l == x && r == y) return t[p];
  pushdown(p);
  int mid = (l + r) >> 1;
  node res;
  if (y <= mid)
    res = query(l, mid, x, y, p << 1);
  else if (x > mid)
    res = query(mid + 1, r, x, y, p << 1 | 1);
  else
    pushup(res, query(l, mid, x, mid, p << 1),
           query(mid + 1, r, mid + 1, y, p << 1 | 1));
  return res;
}
void rev(int l, int r, int x, int y, int p) {
  if (x <= l && r <= y) {
    t[p].tag ^= 1;
    rev(p);
    return;
  }
  pushdown(p);
  int mid = (l + r) >> 1;
  if (x <= mid) rev(l, mid, x, y, p << 1);
  if (y > mid) rev(mid + 1, r, x, y, p << 1 | 1);
  pushup(t[p], t[p << 1], t[p << 1 | 1]);
}
void solve() {
  build(1, n, 1);
  int q = read();
  int op, x, y, k, l, r;
  node tmp;
  while (q--) {
    op = read();
    if (op == 0) {
      x = read(), y = read();
      update(1, n, x, y, 1);
    } else {
      x = read(), y = read(), k = read();
      int ans = 0;
      for (int i = (int)1; i <= (int)k; i++) {
        tmp = query(1, n, x, y, 1);
        c[i] = tmp;
        ans += tmp.mx;
        l = c[i].mx_l, r = c[i].mx_r;
        if (1 <= l && l <= r && r <= n) rev(1, n, l, r, 1);
      }
      printf("%d\n", ans);
      for (int i = (int)1; i <= (int)k; i++) {
        l = c[i].mx_l, r = c[i].mx_r;
        if (1 <= l && l <= r && r <= n) rev(1, n, l, r, 1);
      }
    }
  }
}
int main() {
  init();
  solve();
  return 0;
}
