#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <typename T>
void read(T &x);
template <typename T>
void read(T &x, T &y);
template <typename T>
void read(T &x, T &y, T &z);
template <typename T>
void write(T x);
template <typename T>
void writeC(T x);
template <typename T>
void writeN(T x);
int n, k, a[100005], q, opt, l, r, x, y;
long long ans;
struct data {
  int l1, r1, l2, r2, L1, R1, L2, R2;
  long long v1, v2, lv1, lv2, rv1, rv2, sum;
};
data merge(data x, data y) {
  data z;
  z.v1 = std::max({x.v1, y.v1, x.rv1 + y.lv1});
  z.v2 = std::min({x.v2, y.v2, x.rv2 + y.lv2});
  z.lv1 = std::max(x.lv1, x.sum + y.lv1);
  z.rv1 = std::max(y.rv1, y.sum + x.rv1);
  z.lv2 = std::min(x.lv2, x.sum + y.lv2);
  z.rv2 = std::min(y.rv2, y.sum + x.rv2);
  z.sum = x.sum + y.sum;
  if (z.v1 == x.v1) {
    z.l1 = x.l1;
    z.r1 = x.r1;
  }
  if (z.v1 == y.v1) {
    z.l1 = y.l1;
    z.r1 = y.r1;
  }
  if (z.v1 == x.rv1 + y.lv1) {
    z.l1 = x.R1;
    z.r1 = y.L1;
  }
  if (z.v2 == x.v2) {
    z.l2 = x.l2;
    z.r2 = x.r2;
  }
  if (z.v2 == y.v2) {
    z.l2 = y.l2;
    z.r2 = y.r2;
  }
  if (z.v2 == x.rv2 + y.lv2) {
    z.l2 = x.R2;
    z.r2 = y.L2;
  }
  if (z.lv1 == x.lv1) {
    z.L1 = x.L1;
  } else
    z.L1 = y.L1;
  if (z.rv1 == y.rv1)
    z.R1 = y.R1;
  else
    z.R1 = x.R1;
  if (z.lv2 == x.lv2) {
    z.L2 = x.L2;
  } else
    z.L2 = y.L2;
  if (z.rv2 == y.rv2)
    z.R2 = y.R2;
  else
    z.R2 = x.R2;
  return z;
}
data revr(data x) {
  std::swap(x.l1, x.l2);
  std::swap(x.r1, x.r2);
  std::swap(x.L1, x.L2);
  std::swap(x.R1, x.R2);
  std::swap(x.v1, x.v2);
  std::swap(x.lv1, x.lv2);
  std::swap(x.rv1, x.rv2);
  x.v1 = -x.v1;
  x.v2 = -x.v2;
  x.lv1 = -x.lv1;
  x.lv2 = -x.lv2;
  x.rv1 = -x.rv1;
  x.rv2 = -x.rv2;
  x.sum = -x.sum;
  return x;
}
struct iloveccf {
  data sum[100005 << 2];
  int tag[100005 << 2] = {0};
  void update(int x) { sum[x] = merge(sum[x << 1], sum[x << 1 | 1]); }
  void build(int l, int r, int rt) {
    if (l == r) {
      sum[rt] = data(
          {l, l, l, l, l, l, l, l, a[l], a[l], a[l], a[l], a[l], a[l], a[l]});
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    update(rt);
  }
  void rev(int x) {
    sum[x] = revr(sum[x]);
    tag[x] ^= 1;
  }
  void pushdown(int x) {
    if (!tag[x]) return;
    rev(x << 1);
    rev(x << 1 | 1);
    tag[x] = 0;
  }
  void reverse(int l, int r, int L, int R, int rt) {
    if (l > R || r < L) return;
    if (l <= L && R <= r) {
      rev(rt);
      return;
    }
    pushdown(rt);
    int mid = (L + R) >> 1;
    reverse(l, r, L, mid, rt << 1);
    reverse(l, r, mid + 1, R, rt << 1 | 1);
    update(rt);
  }
  void modify(int l, int r, int p, int v, int rt) {
    if (l == r) {
      sum[rt] = data({l, l, l, l, l, l, l, l, v, v, v, v, v, v, v});
      return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (p <= mid)
      modify(l, mid, p, v, rt << 1);
    else
      modify(mid + 1, r, p, v, rt << 1 | 1);
    update(rt);
  }
  data query(int l, int r, int L, int R, int rt) {
    if (l <= L && R <= r) return sum[rt];
    int mid = (L + R) >> 1;
    pushdown(rt);
    if (l <= mid && r > mid)
      return merge(query(l, r, L, mid, rt << 1),
                   query(l, r, mid + 1, R, rt << 1 | 1));
    else if (l <= mid)
      return query(l, r, L, mid, rt << 1);
    else
      return query(l, r, mid + 1, R, rt << 1 | 1);
  }
} ccf;
void answer(int l, int r, int k) {
  long long ans = 0;
  std::stack<std::pair<int, int> > stk;
  while (k--) {
    data d = ccf.query(l, r, 1, n, 1);
    if (d.v1 <= 0) break;
    ans += d.v1;
    stk.push(std::make_pair(d.l1, d.r1));
    ccf.reverse(d.l1, d.r1, 1, n, 1);
  }
  while (!stk.empty()) {
    std::pair<int, int> p = stk.top();
    stk.pop();
    ccf.reverse(p.first, p.second, 1, n, 1);
  }
  printf("%lld\n", ans);
}
int main() {
  read(n);
  for (int i = 1; i <= (n); ++i) read(a[i]);
  ;
  ccf.build(1, n, 1);
  read(q);
  while (q--) {
    read(opt);
    if (opt == 1) {
      read(l, r, k);
      answer(l, r, k);
    } else {
      read(x, y);
      ccf.modify(1, n, x, y, 1);
    }
  }
  return 0;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T flag = 1;
  while (c < '0' || c > '9') {
    if (c == '-') flag = -flag;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <typename T>
void read(T &x, T &y, T &z) {
  read(x);
  read(y);
  read(z);
}
template <typename T>
void writeC(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) writeC(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void write(T x) {
  writeC(x);
  putchar(' ');
}
template <typename T>
void writeN(T x) {
  writeC(x);
  puts("");
}
