#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int maxk = 25;
const int INF = 1 << 30;
int read() {
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  int x, tag;
  if (ch == '-')
    x = 0, tag = -1;
  else
    x = ch - '0', tag = 1;
  ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * tag;
}
void writeln(int x) {
  if (!x)
    putchar('0');
  else {
    if (x < 0) putchar('-'), x = abs(x);
    int ch[30], l = 0;
    while (x) ch[l++] = x % 10, x /= 10;
    while (l) putchar(ch[--l] + '0');
  }
  putchar('\n');
}
struct ans {
  int p1, p2, p3, p4, l, r, all, sum;
  void insert(int p, int v) {
    l = r = all = sum = v;
    p1 = p2 = p3 = p4 = p;
  }
};
ans merge_max(ans x, ans y) {
  ans c;
  if (x.l > y.l + x.sum) {
    c.l = x.l;
    c.p1 = x.p1;
  } else {
    c.l = x.sum + y.l;
    c.p1 = y.p1;
  }
  if (y.r > x.r + y.sum) {
    c.r = y.r;
    c.p2 = y.p2;
  } else {
    c.r = y.sum + x.r;
    c.p2 = x.p2;
  }
  c.all = max(x.all, y.all);
  c.all = max(c.all, x.r + y.l);
  if (c.all == x.all)
    c.p3 = x.p3, c.p4 = x.p4;
  else {
    if (c.all == y.all)
      c.p3 = y.p3, c.p4 = y.p4;
    else
      c.p3 = x.p2, c.p4 = y.p1;
  }
  c.sum = x.sum + y.sum;
  return c;
}
ans merge_min(ans x, ans y) {
  ans c;
  if (x.l < y.l + x.sum) {
    c.l = x.l;
    c.p1 = x.p1;
  } else {
    c.l = x.sum + y.l;
    c.p1 = y.p1;
  }
  if (y.r < x.r + y.sum) {
    c.r = y.r;
    c.p2 = y.p2;
  } else {
    c.r = y.sum + x.r;
    c.p2 = x.p2;
  }
  c.all = min(x.all, y.all);
  c.all = min(c.all, x.r + y.l);
  if (c.all == x.all)
    c.p3 = x.p3, c.p4 = x.p4;
  else {
    if (c.all == y.all)
      c.p3 = y.p3, c.p4 = y.p4;
    else
      c.p3 = x.p2, c.p4 = y.p1;
  }
  c.sum = x.sum + y.sum;
  return c;
}
struct node {
  int ch[2], l, r, sum;
  bool tag;
  ans v1, v2;
  node() {
    ch[0] = ch[1] = sum = 0;
    v1.l = v1.r = v1.all = INF;
    v2.l = v2.r = v2.all = -INF;
    v1.sum = v2.sum = 0;
  }
} z[maxn * 2];
int rt, treesize = 0;
int w[maxn];
void update(int a) {
  z[a].sum = z[z[a].ch[0]].sum + z[z[a].ch[1]].sum;
  z[a].v1 = merge_min(z[z[a].ch[0]].v1, z[z[a].ch[1]].v1);
  z[a].v2 = merge_max(z[z[a].ch[0]].v2, z[z[a].ch[1]].v2);
}
void build(int &a, int l, int r) {
  a = ++treesize;
  z[a].l = l, z[a].r = r;
  if (l == r) {
    z[a].sum = w[l];
    z[a].v1.insert(l, w[l]);
    z[a].v2.insert(l, w[l]);
    return;
  }
  int m = (l + r) >> 1;
  build(z[a].ch[0], l, m);
  build(z[a].ch[1], m + 1, r);
  update(a);
}
void pushup(int a) {
  if (z[a].l == z[a].r) {
    z[a].v1.insert(z[a].l, -z[a].sum);
    z[a].v2.insert(z[a].l, -z[a].sum);
    z[a].sum *= -1;
    return;
  }
  z[a].tag ^= 1;
  swap(z[a].v1, z[a].v2);
  z[a].v1.l *= -1;
  z[a].v1.r *= -1;
  z[a].v1.all *= -1;
  z[a].v1.sum *= -1;
  z[a].v2.l *= -1;
  z[a].v2.r *= -1;
  z[a].v2.all *= -1;
  z[a].v2.sum *= -1;
  z[a].sum *= -1;
}
void pushdown(int a) {
  if (z[a].tag) {
    z[a].tag = 0;
    pushup(z[a].ch[0]);
    pushup(z[a].ch[1]);
  }
}
ans query(int a, int l, int r) {
  if (z[a].l == l && z[a].r == r) return z[a].v2;
  pushdown(a);
  int m = (z[a].l + z[a].r) >> 1;
  if (r <= m) return query(z[a].ch[0], l, r);
  if (l > m) return query(z[a].ch[1], l, r);
  return merge_max(query(z[a].ch[0], l, m), query(z[a].ch[1], m + 1, r));
}
void get_tag(int a, int l, int r) {
  if (z[a].l == l && z[a].r == r) {
    pushup(a);
    return;
  }
  pushdown(a);
  int m = (z[a].l + z[a].r) >> 1;
  if (r <= m)
    get_tag(z[a].ch[0], l, r);
  else {
    if (l > m)
      get_tag(z[a].ch[1], l, r);
    else
      get_tag(z[a].ch[0], l, m), get_tag(z[a].ch[1], m + 1, r);
  }
  update(a);
}
void modify(int a, int p, int v) {
  if (z[a].l == z[a].r) {
    z[a].sum = v;
    z[a].v1.insert(p, v);
    z[a].v2.insert(p, v);
    return;
  }
  int m = (z[a].l + z[a].r) >> 1;
  if (p <= m)
    modify(z[a].ch[0], p, v);
  else
    modify(z[a].ch[1], p, v);
  update(a);
}
int mx[maxk][2];
void get_ans(int l, int r, int k) {
  int tot = 0, len = 0;
  ans cur;
  for (int i = 0; i < k; ++i) {
    cur = query(rt, l, r);
    if (cur.all <= 0) break;
    len = i + 1;
    tot += cur.all;
    get_tag(rt, cur.p3, cur.p4);
    mx[i][0] = cur.p3;
    mx[i][1] = cur.p4;
  }
  for (int i = 0; i < len; ++i) get_tag(rt, mx[i][0], mx[i][1]);
  writeln(tot);
}
int main() {
  int n, m;
  n = read();
  for (int i = 1; i <= n; ++i) w[i] = read();
  build(rt, 1, n);
  m = read();
  int tag, x, y, z;
  while (m--) {
    tag = read(), x = read(), y = read();
    if (tag == 1) {
      z = read();
      get_ans(x, y, z);
    } else
      modify(rt, x, y);
  }
  return 0;
}
