#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, k, opt, l, r, x, y, q, a[N];
struct Ask {
  int val, l, r;
  Ask(int _val = 0, int _l = 0, int _r = 0) {
    val = _val;
    l = _l;
    r = _r;
  }
};
struct Tree {
  int l, r, flag, sum;
  pair<int, int> lmin, lmax, rmin, rmax;
  Ask num1, num2;
} T[N * 4];
inline Tree merge(Tree x, Tree y) {
  Tree z;
  z.flag = 0;
  z.l = x.l;
  z.r = y.r;
  z.sum = x.sum + y.sum;
  z.lmax = max(x.lmax, make_pair(x.sum + y.lmax.first, y.lmax.second));
  z.lmin = min(x.lmin, make_pair(x.sum + y.lmin.first, y.lmin.second));
  z.rmax = max(y.rmax, make_pair(y.sum + x.rmax.first, x.rmax.second));
  z.rmin = min(y.rmin, make_pair(y.sum + x.rmin.first, x.rmin.second));
  if (x.num1.val > y.num1.val)
    z.num1 = x.num1;
  else
    z.num1 = y.num1;
  if (x.num2.val < y.num2.val)
    z.num2 = x.num2;
  else
    z.num2 = y.num2;
  if (z.num1.val < x.rmax.first + y.lmax.first)
    z.num1 = Ask(x.rmax.first + y.lmax.first, x.rmax.second, y.lmax.second);
  if (z.num2.val > x.rmin.first + y.lmin.first)
    z.num2 = Ask(x.rmin.first + y.lmin.first, x.rmin.second, y.lmin.second);
  return z;
}
void build(int x, int l, int r) {
  if (l == r) {
    T[x].l = T[x].r = r;
    T[x].num1 = Ask(a[l], l, l);
    T[x].num2 = Ask(a[l], l, l);
    T[x].sum = a[l];
    T[x].lmax = T[x].lmin = T[x].rmax = T[x].rmin = make_pair(a[l], l);
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  T[x] = merge(T[x * 2], T[x * 2 + 1]);
}
inline void rev(int x) {
  T[x].flag ^= 1;
  swap(T[x].num1, T[x].num2);
  swap(T[x].lmax, T[x].lmin);
  swap(T[x].rmax, T[x].rmin);
  T[x].num1.val = -T[x].num1.val;
  T[x].num2.val = -T[x].num2.val;
  T[x].lmax.first = -T[x].lmax.first;
  T[x].lmin.first = -T[x].lmin.first;
  T[x].rmax.first = -T[x].rmax.first;
  T[x].rmin.first = -T[x].rmin.first;
  T[x].sum = -T[x].sum;
}
inline void down(int x) {
  if (T[x].flag) {
    T[x].flag = 0;
    rev(x * 2);
    rev(x * 2 + 1);
  }
}
void insert1(int x, int y, int z) {
  if (T[x].l == T[x].r) {
    T[x].num1 = Ask(z, y, y);
    T[x].num2 = Ask(z, y, y);
    T[x].sum = z;
    T[x].lmax = T[x].lmin = T[x].rmax = T[x].rmin = make_pair(z, y);
    return;
  }
  down(x);
  int mid = (T[x].l + T[x].r) / 2;
  if (y <= mid)
    insert1(x * 2, y, z);
  else
    insert1(x * 2 + 1, y, z);
  T[x] = merge(T[x * 2], T[x * 2 + 1]);
}
void insert2(int x, int l, int r) {
  if (T[x].l > r || l > T[x].r) return;
  if (T[x].l >= l && T[x].r <= r) {
    rev(x);
    return;
  }
  down(x);
  insert2(x * 2, l, r);
  insert2(x * 2 + 1, l, r);
  T[x] = merge(T[x * 2], T[x * 2 + 1]);
}
Tree find(int x, int l, int r) {
  if (T[x].l >= l && T[x].r <= r) return T[x];
  down(x);
  int mid = (T[x].l + T[x].r) / 2;
  if (r <= mid) return find(x * 2, l, r);
  if (l > mid) return find(x * 2 + 1, l, r);
  return merge(find(x * 2, l, mid), find(x * 2 + 1, mid + 1, r));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    scanf("%d", &opt);
    if (opt == 0) {
      scanf("%d%d", &x, &y);
      insert1(1, x, y);
    } else {
      scanf("%d%d%d", &l, &r, &k);
      int ans = 0;
      vector<pair<int, int> > v;
      while (k--) {
        Ask num = find(1, l, r).num1;
        if (num.val >= 0) {
          v.push_back(make_pair(num.l, num.r));
          insert2(1, num.l, num.r);
          ans += num.val;
        }
      }
      printf("%d\n", ans);
      for (pair<int, int> i : v) insert2(1, i.first, i.second);
    }
  }
  return 0;
}
