#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, Q, A[maxn];
inline int read() {
  int ret = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -f;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    ret = ret * 10 + ch - '0';
    ch = getchar();
  }
  return ret * f;
}
struct Range {
  int L, R, Sum;
  inline bool operator<(const Range& b) const { return Sum < b.Sum; }
  inline Range operator+(const Range& b) const {
    return (Range){L, b.R, Sum + b.Sum};
  }
} Ra[25];
struct SegmentTree {
  struct Node {
    Range Lmax, Rmax, Max, Lmin, Rmin, Min, All;
    bool Tag;
  } Tree[maxn * 4];
  inline void Merge(Node& a, Node b, Node c) {
    a.All = b.All + c.All;
    a.Lmin = min(b.Lmin, b.All + c.Lmin);
    a.Rmin = min(c.Rmin, b.Rmin + c.All);
    a.Lmax = max(b.Lmax, b.All + c.Lmax);
    a.Rmax = max(c.Rmax, b.Rmax + c.All);
    a.Max = max(max(b.Max, c.Max), b.Rmax + c.Lmax);
    a.Min = min(min(b.Min, c.Min), b.Rmin + c.Lmin);
  }
  inline void PushUp(int rt) {
    Merge(Tree[rt], Tree[rt * 2], Tree[rt * 2 + 1]);
  }
  inline void Reverse(int rt) {
    Tree[rt].Lmin.Sum *= -1;
    Tree[rt].Lmax.Sum *= -1;
    Tree[rt].Rmin.Sum *= -1;
    Tree[rt].Rmax.Sum *= -1;
    Tree[rt].Min.Sum *= -1;
    Tree[rt].Max.Sum *= -1;
    Tree[rt].All.Sum *= -1;
    swap(Tree[rt].Min, Tree[rt].Max);
    swap(Tree[rt].Lmax, Tree[rt].Lmin);
    swap(Tree[rt].Rmax, Tree[rt].Rmin);
  }
  inline void PushDown(int rt) {
    if (Tree[rt].Tag) {
      Reverse(rt * 2);
      Reverse(rt * 2 + 1);
      Tree[rt * 2].Tag ^= 1;
      Tree[rt * 2 + 1].Tag ^= 1;
      Tree[rt].Tag ^= 1;
    }
  }
  inline void Build(int L = 1, int R = n, int rt = 1) {
    if (L == R) {
      Tree[rt].All = Tree[rt].Lmax = Tree[rt].Lmin = Tree[rt].Max =
          Tree[rt].Min = Tree[rt].Rmax = Tree[rt].Rmin = (Range){L, R, A[L]};
      return;
    }
    int M = (L + R) >> 1;
    Build(L, M, rt * 2);
    Build(M + 1, R, rt * 2 + 1);
    PushUp(rt);
  }
  inline void UpdatePoint(int P, int V, int L = 1, int R = n, int rt = 1) {
    if (L == R) {
      Tree[rt].All.Sum = Tree[rt].Lmax.Sum = Tree[rt].Lmin.Sum =
          Tree[rt].Max.Sum = Tree[rt].Min.Sum = Tree[rt].Rmax.Sum =
              Tree[rt].Rmin.Sum = V;
      return;
    }
    int M = (L + R) >> 1;
    PushDown(rt);
    if (P <= M) UpdatePoint(P, V, L, M, rt * 2);
    if (M < P) UpdatePoint(P, V, M + 1, R, rt * 2 + 1);
    PushUp(rt);
  }
  inline Node QueryMax(int LL, int RR, int L = 1, int R = n, int rt = 1) {
    if (LL <= L && R <= RR) return Tree[rt];
    int M = (L + R) >> 1;
    Node ret;
    PushDown(rt);
    if (LL <= M) ret = QueryMax(LL, RR, L, M, rt * 2);
    if (M < RR) {
      if (LL > M)
        ret = QueryMax(LL, RR, M + 1, R, rt * 2 + 1);
      else
        Merge(ret, ret, QueryMax(LL, RR, M + 1, R, rt * 2 + 1));
    }
    return ret;
  }
  inline void UpdateRange(int LL, int RR, int L = 1, int R = n, int rt = 1) {
    if (LL <= L && R <= RR) {
      Reverse(rt);
      Tree[rt].Tag ^= 1;
      return;
    }
    int M = (L + R) >> 1;
    PushDown(rt);
    if (LL <= M) UpdateRange(LL, RR, L, M, rt * 2);
    if (M < RR) UpdateRange(LL, RR, M + 1, R, rt * 2 + 1);
    PushUp(rt);
  }
} S;
int main() {
  n = read();
  for (int i = 1; i <= n; i++) A[i] = read();
  Q = read();
  S.Build();
  while (Q--) {
    if (read() == 0) {
      int P = read(), V = read();
      S.UpdatePoint(P, V);
    } else {
      int L = read(), R = read(), K = read(), cnt, ans = 0;
      for (cnt = 0; cnt < K; cnt++) {
        SegmentTree::Node tep = S.QueryMax(L, R);
        if (tep.Max.Sum <= 0) break;
        ans += tep.Max.Sum;
        S.UpdateRange(tep.Max.L, tep.Max.R);
        Ra[cnt] = tep.Max;
      }
      for (int i = 0; i < cnt; i++) S.UpdateRange(Ra[i].L, Ra[i].R);
      printf("%d\n", ans);
    }
  }
  return 0;
}
