#include <bits/stdc++.h>
const int oo = 0x3f3f3f3f;
template <typename T>
inline bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
std::string procStatus() {
  std::ifstream t("/proc/self/status");
  return std::string(std::istreambuf_iterator<char>(t),
                     std::istreambuf_iterator<char>());
}
template <typename T>
T read(T &first) {
  int f = 1;
  char ch = getchar_unlocked();
  for (; !isdigit(ch); ch = getchar_unlocked())
    if (ch == '-') f = -1;
  for (first = 0; isdigit(ch); ch = getchar_unlocked())
    first = 10 * first + ch - '0';
  return first *= f;
}
template <typename T>
void write(T first) {
  if (first == 0) {
    putchar_unlocked('0');
    return;
  }
  if (first < 0) {
    putchar_unlocked('-');
    first = -first;
  }
  static char s[20];
  int top = 0;
  for (; first; first /= 10) s[++top] = first % 10 + '0';
  while (top) putchar_unlocked(s[top--]);
}
const int MAXN = 1e5 + 5, MAXK = 25;
int N, M;
int A[MAXN];
namespace SEGT {
const int SIZE = MAXN * 4 + 5;
struct Atom {
  int l, r, s;
  Atom() : l(0), r(0), s(0) {}
  Atom(int p, int first) : l(p), r(p), s(first) {}
  Atom(int l_, int r_, int s_) : l(l_), r(r_), s(s_) {}
  friend bool operator<(const Atom &a, const Atom &b) { return a.s < b.s; }
  friend Atom operator+(const Atom &a, const Atom &b) {
    return a.r + 1 == b.l ? Atom(a.l, b.r, a.s + b.s) : Atom();
  }
  void xswap(Atom &first) {
    std::swap(*this, first);
    s = -s;
    first.s = -first.s;
  }
};
struct Node {
  Atom first[2], second[2], z[2], all;
  Atom u[2], v[2], w[2];
  Node() {}
  Node(int p_, int x_) {
    first[0] = second[0] = z[0] = Atom(p_, x_);
    u[0] = v[0] = w[0] = Atom(p_, x_);
    all = Atom(p_, x_);
  }
  void tagRev() {
    first[0].xswap(first[1]);
    u[0].xswap(u[1]);
    std::swap(first[0], u[0]);
    std::swap(first[1], u[1]);
    second[0].xswap(second[1]);
    v[0].xswap(v[1]);
    std::swap(second[0], v[0]);
    std::swap(second[1], v[1]);
    z[0].xswap(z[1]);
    w[0].xswap(w[1]);
    std::swap(z[0], w[0]);
    std::swap(z[1], w[1]);
    all.s = -all.s;
  }
  friend Node operator+(const Node &a, const Node &b) {
    Node ret;
    for (int i = 0; i < 2; ++i) {
      ret.first[i] = std::max(a.first[i], a.all + b.first[i]);
      ret.second[i] = std::max(b.second[i], a.second[i] + b.all);
      ret.z[i] = std::max(std::max(a.z[i], b.z[i]), a.second[i] + b.first[i]);
      ret.u[i] = std::min(a.u[i], a.all + b.u[i]);
      ret.v[i] = std::min(b.v[i], a.v[i] + b.all);
      ret.w[i] = std::min(std::min(a.w[i], b.w[i]), a.v[i] + b.u[i]);
    }
    assert(a.all.r + 1 == b.all.l);
    ret.all = a.all + b.all;
    return ret;
  }
};
Node node[SIZE];
int revt[SIZE];
inline void pushdown(int u) {
  if (revt[u]) {
    node[(u << 1)].tagRev();
    revt[(u << 1)] ^= 1;
    node[(u << 1 | 1)].tagRev();
    revt[(u << 1 | 1)] ^= 1;
    revt[u] = 0;
  }
}
void _modify(int u, int l, int r, int ql, int qr) {
  if (l == r) {
    node[u] = Node(l, A[l]);
    return;
  }
  pushdown(u);
  int mid = (l + r) >> 1;
  if (ql <= mid) _modify((u << 1), l, mid, ql, qr);
  if (mid < qr) _modify((u << 1 | 1), mid + 1, r, ql, qr);
  node[u] = node[(u << 1)] + node[(u << 1 | 1)];
}
Node _query(int u, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return node[u];
  pushdown(u);
  int mid = (l + r) >> 1;
  if (ql <= mid && mid < qr)
    return _query((u << 1), l, mid, ql, qr) +
           _query((u << 1 | 1), mid + 1, r, ql, qr);
  return ql <= mid ? _query((u << 1), l, mid, ql, qr)
                   : _query((u << 1 | 1), mid + 1, r, ql, qr);
}
void _rev(int u, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    node[u].tagRev();
    revt[u] ^= 1;
    return;
  }
  pushdown(u);
  int mid = (l + r) >> 1;
  if (ql <= mid) _rev((u << 1), l, mid, ql, qr);
  if (mid < qr) _rev((u << 1 | 1), mid + 1, r, ql, qr);
  node[u] = node[(u << 1)] + node[(u << 1 | 1)];
}
}  // namespace SEGT
void input() {
  read(N);
  for (int i = 1; i <= N; ++i) {
    read(A[i]);
  }
  read(M);
}
void solve() {
  SEGT::_modify(1, 1, N, 1, N);
  while (M--) {
    int type;
    read(type);
    if (type == 0) {
      int p, val;
      read(p);
      read(val);
      A[p] = val;
      SEGT::_modify(1, 1, N, p, p);
    } else {
      int l, r, k;
      read(l);
      read(r);
      read(k);
      std::pair<int, int> st[MAXK];
      int top = 0;
      int ans = 0;
      while (k--) {
        SEGT::Node t = SEGT::_query(1, 1, N, l, r);
        SEGT::Atom first = std::max(t.z[0], t.z[1]);
        if (first.s <= 0) break;
        SEGT::_rev(1, 1, N, first.l, first.r);
        ans += first.s;
        st[++top] = std::make_pair(first.l, first.r);
      }
      for (; top > 0; --top) {
        SEGT::_rev(1, 1, N, st[top].first, st[top].second);
      }
      printf("%d\n", ans);
    }
  }
}
int main() {
  input();
  solve();
  return 0;
}
