#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void RST(T &A, char x = 0) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void SRT(T &A) {
  sort(A.begin(), A.end());
}
template <class T, class C>
inline void SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
}
const int DX[4] = {1, -1, 0, 0};
const int DY[4] = {0, 0, -1, 1};
const int inf = 0x3f3f3f3f;
const long long linf = 1LL << 60;
const double eps = 1e-9;
const double oo = 1e70;
const double pi = acos(-1.0);
inline double dcmp(const double &x) { return (x > eps) - (x < -eps); }
inline double dcmp(const double &x, const double &y) { return dcmp(x - y); }
template <class T>
inline void RD(T &x) {
  char c = getchar();
  x = 0;
  int flg = 0;
  while (c < '0' || c > '9') flg |= c == '-', c = getchar();
  while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();
  if (flg) x = -x;
}
template <class T1, class T2>
inline void RD(T1 &x, T2 &y) {
  RD(x);
  RD(y);
}
template <class T1, class T2, class T3>
inline void RD(T1 &x, T2 &y, T3 &z) {
  RD(x);
  RD(y);
  RD(z);
}
template <class T1, class T2, class T3, class T4>
inline void RD(T1 &x, T2 &y, T3 &z, T4 &w) {
  RD(x);
  RD(y);
  RD(z);
  RD(w);
}
inline long long RD() {
  long long x;
  RD(x);
  return x;
}
inline void OT(int x) { printf("%d\n", x); }
inline void OT(long long x) { printf("%I6d\n", x); }
inline void OT(int x, int y) { printf("%d %d\n", x, y); }
inline void OT(long long x, long long y) { printf("%I6d %I6d\n", x, y); }
inline void setIO(char *in, char *out) {
  if (in) freopen(in, "r", stdin);
  if (out) freopen(out, "w", stdout);
}
template <class T>
inline void upmax(T &ans, const T &x) {
  ans = max(ans, x);
}
template <class T>
inline void upmin(T &ans, const T &x) {
  ans = min(ans, x);
}
inline char getAlpha() {
  char c = getchar();
  while (c < 'A' || c > 'Z') c = getchar();
  return c;
}
inline char getalpha() {
  char c = getchar();
  while (c < 'a' || c > 'z') c = getchar();
  return c;
}
const int maxn = 100000 + 5;
int N, M, A[maxn];
struct Msg {
  int sm, mx, mn, lmx, lmn, rmx, rmn, lmxr, rmxl, mxl, mxr, lmnr, rmnl, mnl,
      mnr;
  Msg() {}
  Msg(int sm) : sm(sm) {}
  inline void setV(int x, int v) {
    sm = mx = lmx = rmx = mn = lmn = rmn = v;
    lmxr = rmxl = lmnr = rmnl = mxl = mxr = mnl = mnr = x;
  }
  inline Msg operator+(const Msg &b) const {
    Msg c;
    if (sm == -inf) return b;
    if (b.sm == -inf) return *this;
    c.sm = sm + b.sm;
    if (sm + b.lmx > lmx)
      c.lmx = sm + b.lmx, c.lmxr = b.lmxr;
    else
      c.lmx = lmx, c.lmxr = lmxr;
    if (rmx + b.sm > b.rmx)
      c.rmx = rmx + b.sm, c.rmxl = rmxl;
    else
      c.rmx = b.rmx, c.rmxl = b.rmxl;
    if (rmx + b.lmx > max(mx, b.mx))
      c.mx = rmx + b.lmx, c.mxl = rmxl, c.mxr = b.lmxr;
    else {
      if (mx > b.mx)
        c.mx = mx, c.mxl = mxl, c.mxr = mxr;
      else
        c.mx = b.mx, c.mxl = b.mxl, c.mxr = b.mxr;
    }
    if (sm + b.lmn < lmn)
      c.lmn = sm + b.lmn, c.lmnr = b.lmnr;
    else
      c.lmn = lmn, c.lmnr = lmnr;
    if (rmn + b.sm < b.rmn)
      c.rmn = rmn + b.sm, c.rmnl = rmnl;
    else
      c.rmn = b.rmn, c.rmnl = b.rmnl;
    if (rmn + b.lmn < min(mn, b.mn))
      c.mn = rmn + b.lmn, c.mnl = rmnl, c.mnr = b.lmnr;
    else {
      if (mn < b.mn)
        c.mn = mn, c.mnl = mnl, c.mnr = mnr;
      else
        c.mn = b.mn, c.mnl = b.mnl, c.mnr = b.mnr;
    }
    return c;
  }
  inline void do_rev() {
    swap(lmx, lmn), swap(lmxr, lmnr), swap(rmx, rmn), swap(rmxl, rmnl),
        swap(mx, mn), swap(mxl, mnl), swap(mxr, mnr);
    sm = -sm;
    mx = -mx, mn = -mn, lmx = -lmx, lmn = -lmn, rmx = -rmx, rmn = -rmn;
  }
};
namespace SegTree {
struct TNode {
  Msg msg;
  bool rev;
} T[maxn << 2];
inline void do_rev(int rt) {
  T[rt].rev ^= 1;
  T[rt].msg.do_rev();
}
inline void pd(int rt) {
  if (T[rt].rev) do_rev((rt << 1)), do_rev((rt << 1 | 1)), T[rt].rev = 0;
}
inline void maintain(int rt) {
  T[rt].msg = (T[(rt << 1)]).msg + (T[(rt << 1 | 1)]).msg;
}
void buildTree(int rt, int l, int r) {
  if (l == r) {
    T[rt].msg.setV(l, A[l]);
    return;
  }
  int mid = l + r >> 1;
  buildTree((rt << 1), l, mid);
  buildTree((rt << 1 | 1), mid + 1, r);
  maintain(rt);
}
void rev(int rt, int L, int R, int l, int r) {
  if (l > R || r < L) return;
  if (L != R) pd(rt);
  if (l <= L && R <= r) {
    do_rev(rt);
    return;
  }
  int mid = L + R >> 1;
  rev((rt << 1), L, mid, l, r);
  rev((rt << 1 | 1), mid + 1, R, l, r);
  maintain(rt);
}
Msg qur(int rt, int L, int R, int l, int r) {
  if (l > R || r < L) return Msg(-inf);
  if (L != R) pd(rt);
  if (l <= L && R <= r) return T[rt].msg;
  int mid = L + R >> 1;
  return qur((rt << 1), L, mid, l, r) + qur((rt << 1 | 1), mid + 1, R, l, r);
}
void modify(int rt, int L, int R, int x, int v) {
  if (L == R) {
    T[rt].msg.setV(x, v);
    return;
  }
  pd(rt);
  int mid = L + R >> 1;
  if (x <= mid)
    modify((rt << 1), L, mid, x, v);
  else
    modify((rt << 1 | 1), mid + 1, R, x, v);
  maintain(rt);
}
}  // namespace SegTree
int main() {
  RD(N);
  for (int i = 1; i <= int(N); i++) RD(A[i]);
  SegTree::buildTree(1, 1, N);
  int T___;
  RD(T___);
  for (int __n__LINE__ = T___; __n__LINE__--;) {
    int opt = RD(), l, r, x, k;
    if (opt) {
      static int L[30], R[30];
      RD(l, r, x);
      int ans = 0, tot = 0;
      for (int __n__LINE__ = x; __n__LINE__--;) {
        Msg m = SegTree::qur(1, 1, N, l, r);
        if (m.mx <= 0) break;
        ans += m.mx;
        SegTree::rev(1, 1, N, m.mxl, m.mxr), L[++tot] = m.mxl, R[tot] = m.mxr;
      }
      OT(ans);
      for (int i = 1; i <= int(tot); i++) SegTree::rev(1, 1, N, L[i], R[i]);
    } else
      RD(x, k), SegTree::modify(1, 1, N, x, k);
  }
  return 0;
}
