#include <bits/stdc++.h>
using namespace std;
void Get(int &T) {
  char C;
  bool F = 0;
  for (; C = getchar(), C < '0' || C > '9';)
    if (C == '-') F = 1;
  for (T = C - '0'; C = getchar(), C >= '0' && C <= '9'; T = T * 10 + C - '0')
    ;
  F && (T = -T);
}
int N;
int A[1000005];
void Init() {
  Get(N);
  for (int i = 1; i <= N; i++) Get(A[i]);
}
struct Tr {
  int L, R;
  int Min, LMin, RMin;
  int Max, LMax, RMax, Sum;
  int MinL, MinR;
  int LMinR;
  int RMinL;
  int MaxL, MaxR;
  int LMaxR;
  int RMaxL;
  bool Masked;
} T[1000005];
int Top;
void Down(int X) {
  if (T[X].Masked) {
    T[X].Masked = 0;
    T[T[X].L].Masked ^= 1;
    T[T[X].R].Masked ^= 1;
    T[X].Sum = -T[X].Sum;
    T[X].Min = -T[X].Min;
    T[X].LMin = -T[X].LMin;
    T[X].RMin = -T[X].RMin;
    T[X].Max = -T[X].Max;
    T[X].LMax = -T[X].LMax;
    T[X].RMax = -T[X].RMax;
    std::swap(T[X].Min, T[X].Max);
    std::swap(T[X].LMin, T[X].LMax);
    std::swap(T[X].RMin, T[X].RMax);
    std::swap(T[X].MinL, T[X].MaxL);
    std::swap(T[X].MinR, T[X].MaxR);
    std::swap(T[X].LMinR, T[X].LMaxR);
    std::swap(T[X].RMinL, T[X].RMaxL);
  }
}
void Update(Tr &TX, Tr &TL, Tr &TR) {
  TX.Min = TL.Min;
  TX.MinL = TL.MinL;
  TX.MinR = TL.MinR;
  if (TX.Min > TR.Min) {
    TX.Min = TR.Min;
    TX.MinL = TR.MinL;
    TX.MinR = TR.MinR;
  }
  if (TX.Min > TL.RMin + TR.LMin) {
    TX.Min = TL.RMin + TR.LMin;
    TX.MinL = TL.RMinL;
    TX.MinR = TR.LMinR;
  }
  TX.LMin = TL.LMin;
  TX.LMinR = TL.LMinR;
  if (TX.LMin > TL.Sum + TR.LMin) {
    TX.LMin = TL.Sum + TR.LMin;
    TX.LMinR = TR.LMinR;
  }
  TX.RMin = TR.RMin;
  TX.RMinL = TR.RMinL;
  if (TX.RMin > TR.Sum + TL.RMin) {
    TX.RMin = TR.Sum + TL.RMin;
    TX.RMinL = TL.RMinL;
  }
  TX.Max = TL.Max;
  TX.MaxL = TL.MaxL;
  TX.MaxR = TL.MaxR;
  if (TX.Max < TR.Max) {
    TX.Max = TR.Max;
    TX.MaxL = TR.MaxL;
    TX.MaxR = TR.MaxR;
  }
  if (TX.Max < TL.RMax + TR.LMax) {
    TX.Max = TL.RMax + TR.LMax;
    TX.MaxL = TL.RMaxL;
    TX.MaxR = TR.LMaxR;
  }
  TX.LMax = TL.LMax;
  TX.LMaxR = TL.LMaxR;
  if (TX.LMax < TL.Sum + TR.LMax) {
    TX.LMax = TL.Sum + TR.LMax;
    TX.LMaxR = TR.LMaxR;
  }
  TX.RMax = TR.RMax;
  TX.RMaxL = TR.RMaxL;
  if (TX.RMax < TR.Sum + TL.RMax) {
    TX.RMax = TR.Sum + TL.RMax;
    TX.RMaxL = TL.RMaxL;
  }
  TX.Sum = TL.Sum + TR.Sum;
}
int Build(int L, int R) {
  ++Top;
  int ID = Top;
  if (L == R) {
    T[ID].Min = T[ID].LMin = T[ID].RMin = T[ID].Max = T[ID].RMax = T[ID].LMax =
        T[ID].Sum = A[L];
    T[ID].MinL = T[ID].MinR = T[ID].LMinR = T[ID].RMinL = T[ID].MaxL =
        T[ID].MaxR = T[ID].LMaxR = T[ID].RMaxL = L;
    return ID;
  }
  int Mid = L + R;
  Mid >>= 1;
  T[ID].L = Build(L, Mid);
  T[ID].R = Build(Mid + 1, R);
  Update(T[ID], T[T[ID].L], T[T[ID].R]);
  return ID;
}
int Root;
void Modify(int Old, int L, int R, int X, int Y) {
  Down(Old);
  if (X <= L && R <= Y) {
    T[Old].Masked ^= 1;
    Down(Old);
    return;
  }
  int Mid = L + R;
  Mid >>= 1;
  if (X <= Mid) Modify(T[Old].L, L, Mid, X, Y);
  if (Mid + 1 <= Y) Modify(T[Old].R, Mid + 1, R, X, Y);
  Down(T[Old].L);
  Down(T[Old].R);
  Update(T[Old], T[T[Old].L], T[T[Old].R]);
}
void Modify3(int Old, int L, int R, int X, int Value) {
  Down(Old);
  if (L == R) {
    T[Old].Min = T[Old].LMin = T[Old].RMin = T[Old].Max = T[Old].RMax =
        T[Old].LMax = T[Old].Sum = Value;
    return;
  }
  int Mid = L + R;
  Mid >>= 1;
  if (X <= Mid) Modify3(T[Old].L, L, Mid, X, Value);
  if (Mid + 1 <= X) Modify3(T[Old].R, Mid + 1, R, X, Value);
  Down(T[Old].L);
  Down(T[Old].R);
  Update(T[Old], T[T[Old].L], T[T[Old].R]);
}
Tr Ask(int Old, int L, int R, int X, int Y) {
  Down(Old);
  if (X <= L && R <= Y) {
    return T[Old];
  }
  int Mid = L + R;
  Mid >>= 1;
  if (X <= Mid && Mid + 1 <= Y) {
    Tr Lf = Ask(T[Old].L, L, Mid, X, Y);
    Tr Rt = Ask(T[Old].R, Mid + 1, R, X, Y);
    Tr Ans;
    Update(Ans, Lf, Rt);
    return Ans;
  }
  if (X <= Mid) return Ask(T[Old].L, L, Mid, X, Y);
  if (Mid + 1 <= Y) return Ask(T[Old].R, Mid + 1, R, X, Y);
}
void Debug() {
  for (int Root = 1; Root <= 1; Root++) {
    printf("%d       %d %d %d %d %d %d %d\n", Root, T[Root].Min, T[Root].LMin,
           T[Root].RMin, T[Root].Max, T[Root].LMax, T[Root].RMax, T[Root].Sum);
    printf("        %d %d %d %d \n", T[Root].MinL, T[Root].MinR, T[Root].LMinR,
           T[Root].RMinL);
  }
}
int Ans;
int Left[1005];
int Right[1005];
int SegTop;
void Solve(int L, int R, int M) {
  Ans = 0;
  SegTop = 0;
  for (int i = 1; i <= M; i++) {
    Tr Ans0 = Ask(Root, 1, N, L, R);
    if (Ans0.Max < 0) break;
    Ans += Ans0.Max;
    Left[++SegTop] = Ans0.MaxL;
    Right[SegTop] = Ans0.MaxR;
    Modify(Root, 1, N, Left[SegTop], Right[SegTop]);
  }
  printf("%d\n", Ans);
  for (int i = 1; i <= SegTop; i++) {
    Modify(Root, 1, N, Left[i], Right[i]);
  }
}
int M;
void Work() {
  Root = Build(1, N);
  Get(M);
  for (int i = 1, Q, X, Y, L, R, K; i <= M; i++) {
    Get(Q);
    if (Q == 0) {
      Get(X), Get(Y);
      Modify3(Root, 1, N, X, Y);
    } else {
      Get(L), Get(R);
      Get(K);
      Solve(L, R, K);
    }
  }
}
int main() {
  Init();
  Work();
}
