#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000 + 7;
template <class T>
inline void read(T &x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      f = -1;
    }
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  x *= f;
}
int n, m;
int a[100000 + 5];
int L[100000 + 5], R[100000 + 5];
struct node {
  int l, r, val;
};
struct SegTree {
  int l, r;
  node lmax, rmax, qmax, lmin, rmin, qmin;
  int tag;
  int sum;
};
SegTree tr[100000 + 5 << 2];
void pushup(int p) {
  tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
  if (tr[p << 1].lmax.val >= tr[p << 1].sum + tr[p << 1 | 1].lmax.val) {
    tr[p].lmax = tr[p << 1].lmax;
  } else {
    tr[p].lmax.val = tr[p << 1].sum + tr[p << 1 | 1].lmax.val,
    tr[p].lmax.l = tr[p << 1].l, tr[p].lmax.r = tr[p << 1 | 1].lmax.r;
  }
  if (tr[p << 1 | 1].rmax.val >= tr[p << 1].rmax.val + tr[p << 1 | 1].sum) {
    tr[p].rmax = tr[p << 1 | 1].rmax;
  } else {
    tr[p].rmax.val = tr[p << 1].rmax.val + tr[p << 1 | 1].sum,
    tr[p].rmax.l = tr[p << 1].rmax.l, tr[p].rmax.r = tr[p << 1 | 1].r;
  }
  tr[p].qmax.val = max(max(tr[p << 1].qmax.val, tr[p << 1 | 1].qmax.val),
                       tr[p << 1].rmax.val + tr[p << 1 | 1].lmax.val);
  if (tr[p].qmax.val == tr[p << 1].qmax.val) {
    tr[p].qmax = tr[p << 1].qmax;
  } else if (tr[p].qmax.val == tr[p << 1 | 1].qmax.val) {
    tr[p].qmax = tr[p << 1 | 1].qmax;
  } else {
    tr[p].qmax.l = tr[p << 1].rmax.l, tr[p].qmax.r = tr[p << 1 | 1].lmax.r;
  }
  if (tr[p << 1].lmin.val <= tr[p << 1].sum + tr[p << 1 | 1].lmin.val) {
    tr[p].lmin = tr[p << 1].lmin;
  } else {
    tr[p].lmin.val = tr[p << 1].sum + tr[p << 1 | 1].lmin.val,
    tr[p].lmin.l = tr[p << 1].l, tr[p].lmin.r = tr[p << 1 | 1].lmin.r;
  }
  if (tr[p << 1 | 1].rmin.val <= tr[p << 1].rmin.val + tr[p << 1 | 1].sum) {
    tr[p].rmin = tr[p << 1 | 1].rmin;
  } else {
    tr[p].rmin.val = tr[p << 1].rmin.val + tr[p << 1 | 1].sum,
    tr[p].rmin.l = tr[p << 1].rmin.l, tr[p].rmin.r = tr[p << 1 | 1].r;
  }
  tr[p].qmin.val = min(min(tr[p << 1].qmin.val, tr[p << 1 | 1].qmin.val),
                       tr[p << 1].rmin.val + tr[p << 1 | 1].lmin.val);
  if (tr[p].qmin.val == tr[p << 1].qmin.val) {
    tr[p].qmin = tr[p << 1].qmin;
  } else if (tr[p].qmin.val == tr[p << 1 | 1].qmin.val) {
    tr[p].qmin = tr[p << 1 | 1].qmin;
  } else {
    tr[p].qmin.l = tr[p << 1].rmin.l, tr[p].qmin.r = tr[p << 1 | 1].lmin.r;
  }
}
void build(int p, int l, int r) {
  tr[p].l = l, tr[p].r = r;
  tr[p].tag = 0;
  if (l == r) {
    tr[p].lmax.val = tr[p].rmax.val = tr[p].sum = tr[p].qmax.val = a[l];
    tr[p].lmax.l = tr[p].rmax.l = tr[p].qmax.l = l;
    tr[p].lmax.r = tr[p].rmax.r = tr[p].qmax.r = l;
    tr[p].lmin.val = tr[p].rmin.val = tr[p].qmin.val = a[l];
    tr[p].lmin.l = tr[p].rmin.l = tr[p].qmin.l = l;
    tr[p].lmin.r = tr[p].rmin.r = tr[p].qmin.r = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  pushup(p);
}
void spread(int p) {
  if (tr[p].tag) {
    tr[p << 1].tag ^= tr[p].tag, tr[p << 1 | 1].tag ^= tr[p].tag;
    tr[p << 1].qmax.val *= -1, tr[p << 1].lmax.val *= -1,
        tr[p << 1].rmax.val *= -1;
    tr[p << 1].qmin.val *= -1, tr[p << 1].lmin.val *= -1,
        tr[p << 1].rmin.val *= -1;
    tr[p << 1 | 1].qmax.val *= -1, tr[p << 1 | 1].lmax.val *= -1,
        tr[p << 1 | 1].rmax.val *= -1;
    tr[p << 1 | 1].qmin.val *= -1, tr[p << 1 | 1].lmin.val *= -1,
        tr[p << 1 | 1].rmin.val *= -1;
    swap(tr[p << 1].qmax, tr[p << 1].qmin),
        swap(tr[p << 1].lmax, tr[p << 1].lmin),
        swap(tr[p << 1].rmax, tr[p << 1].rmin);
    swap(tr[p << 1 | 1].qmax, tr[p << 1 | 1].qmin),
        swap(tr[p << 1 | 1].lmax, tr[p << 1 | 1].lmin),
        swap(tr[p << 1 | 1].rmax, tr[p << 1 | 1].rmin);
    tr[p << 1].sum *= -1, tr[p << 1 | 1].sum *= -1;
    tr[p].tag = 0;
  }
}
void modify(int p, int x, int val) {
  if (tr[p].l == tr[p].r) {
    tr[p].qmax.val = val, tr[p].qmin.val = val;
    tr[p].lmax.val = val, tr[p].rmax.val = val;
    tr[p].lmin.val = val, tr[p].rmin.val = val;
    tr[p].sum = val;
    return;
  }
  spread(p);
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (x <= mid) {
    modify(p << 1, x, val);
  } else {
    modify(p << 1 | 1, x, val);
  }
  pushup(p);
}
SegTree query(int p, int l, int r) {
  if (l <= tr[p].l && tr[p].r <= r) {
    return tr[p];
  }
  spread(p);
  SegTree res;
  res.qmax.val = -INF;
  SegTree A, B;
  A.sum = B.sum = -INF;
  A.lmax.val = A.rmax.val = A.qmax.val = -INF;
  A.lmin.val = A.rmin.val = A.qmin.val = -INF;
  B.lmax.val = B.rmax.val = B.qmax.val = -INF;
  B.lmin.val = B.rmin.val = B.qmin.val = -INF;
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (l <= mid && r > mid) {
    A = query(p << 1, l, r), B = query(p << 1 | 1, l, r);
    res.sum = A.sum + B.sum;
    if (A.lmax.val >= A.sum + B.lmax.val) {
      res.lmax = A.lmax;
    } else {
      res.lmax.val = A.sum + B.lmax.val, res.lmax.l = A.l,
      res.lmax.r = B.lmax.r;
    }
    if (B.rmax.val >= A.rmax.val + B.sum) {
      res.rmax = B.rmax;
    } else {
      res.rmax.val = A.rmax.val + B.sum, res.rmax.l = A.rmax.l,
      res.rmax.r = B.r;
    }
    res.qmax.val = max(max(A.qmax.val, B.qmax.val), A.rmax.val + B.lmax.val);
    if (res.qmax.val == A.qmax.val) {
      res.qmax = A.qmax;
    } else if (res.qmax.val == B.qmax.val) {
      res.qmax = B.qmax;
    } else {
      res.qmax.l = A.rmax.l, res.qmax.r = B.lmax.r;
    }
    return res;
  }
  if (l <= mid) {
    A = query(p << 1, l, r);
    return A;
  }
  if (r > mid) {
    B = query(p << 1 | 1, l, r);
    return B;
  }
}
void doit(int p, int l, int r) {
  if (l <= tr[p].l && tr[p].r <= r) {
    tr[p].tag ^= 1;
    tr[p].sum *= -1, tr[p].lmax.val *= -1, tr[p].rmax.val *= -1,
        tr[p].qmax.val *= -1;
    tr[p].lmin.val *= -1, tr[p].rmin.val *= -1, tr[p].qmin.val *= -1;
    swap(tr[p].lmax, tr[p].lmin), swap(tr[p].rmax, tr[p].rmin),
        swap(tr[p].qmax, tr[p].qmin);
    return;
  }
  spread(p);
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (l <= mid) {
    doit(p << 1, l, r);
  }
  if (r > mid) {
    doit(p << 1 | 1, l, r);
  }
  pushup(p);
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
  }
  read(m);
  int ope, x, y, k;
  build(1, 1, n);
  while (m--) {
    read(ope);
    if (ope == 0) {
      read(x), read(y);
      modify(1, x, y);
    }
    if (ope == 1) {
      read(x), read(y), read(k);
      long long ans = 0, dat = 0;
      SegTree p;
      for (int j = 1; j <= k; j++) {
        p = query(1, x, y);
        L[j] = p.qmax.l, R[j] = p.qmax.r;
        dat += p.qmax.val;
        ans = max(ans, dat);
        doit(1, L[j], R[j]);
      }
      for (int j = k; j >= 1; j--) {
        doit(1, L[j], R[j]);
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}
