#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  while (c < '0' || c > '9') f |= c == '-', c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
  return f ? -x : x;
}
int N, A[100000 + 5];
struct SegmentTree {
  struct Node {
    int l, r;
    int Sum;
    int MaxBgS, MinBgS, MaxBgPos, MinBgPos;
    int MaxEdS, MinEdS, MaxEdPos, MinEdPos;
    int MaxSbS, MinSbS, MaxSbL, MaxSbR, MinSbL, MinSbR;
    bool flag;
    inline void Rev() {
      Sum = -Sum, flag ^= 1;
      swap(MaxBgS, MinBgS), MaxBgS = -MaxBgS, MinBgS = -MinBgS,
                            swap(MaxBgPos, MinBgPos);
      swap(MaxEdS, MinEdS), MaxEdS = -MaxEdS, MinEdS = -MinEdS,
                            swap(MaxEdPos, MinEdPos);
      swap(MaxSbS, MinSbS), MaxSbS = -MaxSbS, MinSbS = -MinSbS,
                            swap(MaxSbL, MinSbL), swap(MaxSbR, MinSbR);
    }
    inline void Set(int x, int pos) {
      Sum = MaxBgS = MinBgS = MaxEdS = MinEdS = MaxSbS = MinSbS = x;
      MaxBgPos = MinBgPos = MaxEdPos = MinEdPos = MaxSbL = MaxSbR = MinSbL =
          MinSbR = pos;
    }
  } Tree[(100000 << 2) + 5];
  inline void PushUp(Node &A, Node B, Node C) {
    A.Sum = B.Sum + C.Sum;
    if (max(B.MaxSbS, C.MaxSbS) > B.MaxEdS + C.MaxBgS) {
      if (B.MaxSbS > C.MaxSbS)
        A.MaxSbS = B.MaxSbS, A.MaxSbL = B.MaxSbL, A.MaxSbR = B.MaxSbR;
      else
        A.MaxSbS = C.MaxSbS, A.MaxSbL = C.MaxSbL, A.MaxSbR = C.MaxSbR;
    } else
      A.MaxSbS = B.MaxEdS + C.MaxBgS, A.MaxSbL = B.MaxEdPos,
      A.MaxSbR = C.MaxBgPos;
    if (min(B.MinSbS, C.MinSbS) < B.MinEdS + C.MinBgS) {
      if (B.MinSbS < C.MinSbS)
        A.MinSbS = B.MinSbS, A.MinSbL = B.MinSbL, A.MinSbR = B.MinSbR;
      else
        A.MinSbS = C.MinSbS, A.MinSbL = C.MinSbL, A.MinSbR = C.MinSbR;
    } else
      A.MinSbS = B.MinEdS + C.MinBgS, A.MinSbL = B.MinEdPos,
      A.MinSbR = C.MinBgPos;
    if (B.Sum + C.MaxBgS > B.MaxBgS)
      A.MaxBgS = B.Sum + C.MaxBgS, A.MaxBgPos = C.MaxBgPos;
    else
      A.MaxBgS = B.MaxBgS, A.MaxBgPos = B.MaxBgPos;
    if (B.Sum + C.MinBgS < B.MinBgS)
      A.MinBgS = B.Sum + C.MinBgS, A.MinBgPos = C.MinBgPos;
    else
      A.MinBgS = B.MinBgS, A.MinBgPos = B.MinBgPos;
    if (C.Sum + B.MaxEdS > C.MaxEdS)
      A.MaxEdS = C.Sum + B.MaxEdS, A.MaxEdPos = B.MaxEdPos;
    else
      A.MaxEdS = C.MaxEdS, A.MaxEdPos = C.MaxEdPos;
    if (C.Sum + B.MinEdS < C.MinEdS)
      A.MinEdS = C.Sum + B.MinEdS, A.MinEdPos = B.MinEdPos;
    else
      A.MinEdS = C.MinEdS, A.MinEdPos = C.MinEdPos;
  }
  inline void PushDown(int i) {
    if (Tree[i].flag) {
      Tree[i].flag = 0;
      Tree[(i << 1)].Rev(), Tree[(i << 1 | 1)].Rev();
    }
  }
  void Build(int i, int l, int r) {
    Tree[i].l = l, Tree[i].r = r;
    if (l == r) {
      Tree[i].Set(A[l], l);
      return;
    }
    int mid = (l + r) >> 1;
    Build((i << 1), l, mid);
    Build((i << 1 | 1), mid + 1, r);
    PushUp(Tree[i], Tree[(i << 1)], Tree[(i << 1 | 1)]);
  }
  Node Query(int i, int l, int r) {
    if (l <= Tree[i].l && Tree[i].r <= r) return Tree[i];
    PushDown(i);
    int mid = (Tree[i].l + Tree[i].r) >> 1;
    if (mid + 1 <= l) return Query((i << 1 | 1), l, r);
    if (r <= mid) return Query((i << 1), l, r);
    Node ret, L = Query((i << 1), l, r), R = Query((i << 1 | 1), l, r);
    PushUp(ret, L, R);
    return ret;
  }
  void Update(int i, int l, int r) {
    if (r < Tree[i].l || Tree[i].r < l) return;
    if (l <= Tree[i].l && Tree[i].r <= r) {
      Tree[i].Rev();
      return;
    }
    PushDown(i);
    Update((i << 1), l, r);
    Update((i << 1 | 1), l, r);
    PushUp(Tree[i], Tree[(i << 1)], Tree[(i << 1 | 1)]);
  }
  void Modify(int i, int x, int pos) {
    if (pos < Tree[i].l || Tree[i].r < pos) return;
    if (Tree[i].l == Tree[i].r) {
      Tree[i].Set(Tree[i].flag ? -x : x, pos);
      return;
    }
    PushDown(i);
    Modify((i << 1), x, pos);
    Modify((i << 1 | 1), x, pos);
    PushUp(Tree[i], Tree[(i << 1)], Tree[(i << 1 | 1)]);
  }
} T;
pair<int, int> R[20 + 5];
int main() {
  int N = read();
  for (int i = 1; i <= N; i++) A[i] = read();
  T.Build(1, 1, N);
  int Q = read();
  while (Q--) {
    int opt = read();
    if (opt == 0) {
      int pos = read(), val = read();
      T.Modify(1, val, pos);
    } else {
      int Left = read(), Right = read(), K = read(), Ans = 0, cnt = 0;
      while (K--) {
        SegmentTree::Node tmp = T.Query(1, Left, Right);
        if (tmp.MaxSbS <= 0) break;
        Ans += tmp.MaxSbS;
        R[++cnt] = make_pair(tmp.MaxSbL, tmp.MaxSbR);
        T.Update(1, tmp.MaxSbL, tmp.MaxSbR);
      }
      for (int i = 1; i <= cnt; i++) T.Update(1, R[i].first, R[i].second);
      printf("%d\n", Ans);
    }
  }
  return 0;
}
