#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
namespace def {}
namespace tydef {}
namespace io {
const int SIZ = 1 << 21 | 1;
char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110],
                                       c;
int fr;
inline void out() {
  fwrite(obuff, 1, oS - obuff, stdout);
  oS = obuff;
}
template <class Type>
inline void read(Type& x) {
  x = 0;
  Type y = 1;
  for (c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       (c > '9' || c < '0') && c != '-';
       c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
  c == '-' ? y = -1 : x = (c & 15);
  for (c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c >= '0' && c <= '9';
       c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= y;
}
template <class Type>
inline void print(Type x, char text = '\n') {
  if (x < 0) *oS++ = '-', x *= -1;
  if (x == 0) *oS++ = '0';
  while (x) fu[++fr] = x % 10 + '0', x /= 10;
  while (fr) *oS++ = fu[fr--];
  *oS++ = text;
  out();
}
inline void prints(char x[], char text = '\n') {
  for (register int i = 0; x[i]; ++i) *oS++ = x[i];
  *oS++ = text;
  out();
}
}  // namespace io
using namespace tydef;
const int MAX_prime = 0;
namespace Fa {
template <class Type>
inline Type fact(Type n) {
  static Type Fact[55];
  if (n == 1) return Fact[n] = 1;
  if (!Fact[n])
    return Fact[n] = n * fact(n - 1);
  else
    return Fact[n];
}
template <class Type>
inline Type gcd(Type x, Type y) {
  while (x ^= y ^= x ^= y %= x)
    ;
  return y;
}
template <class Type>
Type power(Type x, Type y) {
  Type ans = 1;
  while (y) {
    if (y & 1) ans = ans * x;
    x *= x;
    y >>= 1;
  }
  return ans;
}
}  // namespace Fa
namespace prime {
const int MAX_prime = 1 << 21 | 1;
bool prime_ans[MAX_prime + 10];
int prime_a[MAX_prime + 10];
void is_prime(int n) {
  int flag = 0;
  memset(prime_ans, true, sizeof(prime_ans));
  prime_ans[0] = prime_ans[1] = 0;
  for (long long i = 2; i <= n; i++) {
    if (prime_ans[i]) prime_a[flag++] = i;
    for (long long j = 0; j < flag && i * prime_a[j] <= n; j++) {
      prime_ans[i * prime_a[j]] = 0;
      if (i % prime_a[j] == 0) break;
    }
  }
}
}  // namespace prime
using namespace io;
using namespace Fa;
using namespace def;
using namespace std;
using namespace tydef;
const int mn = 100005;
int val[mn];
bool mark[mn << 2];
struct node {
  int Max_l, l, Max_r, r, Max, L, R, Sum;
} Mx[mn << 2];
node meg(node l, node r) {
  node now = {l.Max_l, l.l, r.Max_r, r.r};
  if (l.Max > r.Max)
    now.Max = l.Max, now.L = l.L, now.R = l.R;
  else
    now.Max = r.Max, now.L = r.L, now.R = r.R;
  if (l.Sum + r.Max_l > now.Max_l) {
    now.Max_l = l.Sum + r.Max_l;
    now.l = r.l;
  }
  if (r.Sum + l.Max_r > now.Max_r) {
    now.Max_r = r.Sum + l.Max_r;
    now.r = l.r;
  }
  if (l.Max_r + r.Max_l > now.Max) {
    now.Max = l.Max_r + r.Max_l;
    now.L = l.r, now.R = r.l;
  }
  now.Sum = l.Sum + r.Sum;
  return now;
}
struct node1 {
  int Min_l, l, Min_r, r, Min, L, R, Sum;
} Mi[mn << 2];
node res(node1 a) {
  return {-a.Min_l, a.l, -a.Min_r, a.r, -a.Min, a.L, a.R, -a.Sum};
}
node1 res(node a) {
  return {-a.Max_l, a.l, -a.Max_r, a.r, -a.Max, a.L, a.R, -a.Sum};
}
void max_up(int o) {
  node l = mark[o << 1] ? res(Mi[o << 1]) : Mx[o << 1];
  node r = mark[o << 1 | 1] ? res(Mi[o << 1 | 1]) : Mx[o << 1 | 1];
  Mx[o] = meg(l, r);
}
node1 meg(node1 l, node1 r) {
  node1 now = {l.Min_l, l.l, r.Min_r, r.r};
  if (l.Min < r.Min)
    now.Min = l.Min, now.L = l.L, now.R = l.R;
  else
    now.Min = r.Min, now.L = r.L, now.R = r.R;
  if (l.Sum + r.Min_l < now.Min_l) {
    now.Min_l = r.Min_l + l.Sum;
    now.l = r.l;
  }
  if (r.Sum + l.Min_r < now.Min_r) {
    now.Min_r = l.Min_r + r.Sum;
    now.r = l.r;
  }
  if (r.Min_l + l.Min_r < now.Min) {
    now.Min = l.Min_r + r.Min_l;
    now.L = l.r, now.R = r.l;
  }
  now.Sum = l.Sum + r.Sum;
  return now;
}
void min_up(int o) {
  node1 l = mark[o << 1] ? res(Mx[o << 1]) : Mi[o << 1];
  node1 r = mark[o << 1 | 1] ? res(Mx[o << 1 | 1]) : Mi[o << 1 | 1];
  Mi[o] = meg(l, r);
}
void up(int o) {
  min_up(o);
  max_up(o);
}
void build(int o, int l, int r) {
  if (l == r) {
    Mx[o] = {val[l], l, val[l], l, val[l], l, l, val[l]};
    Mi[o] = {val[l], l, val[l], l, val[l], l, l, val[l]};
    return;
  }
  int mid = l + r >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  up(o);
}
int y_1, y_2, ad_v;
void change(int o, int l, int r) {
  if (l == r) {
    Mx[o] = {ad_v, l, ad_v, l, ad_v, l, l, ad_v};
    Mi[o] = {ad_v, l, ad_v, l, ad_v, l, l, ad_v};
    return;
  }
  int mid = l + r >> 1;
  if (y_1 <= mid)
    change(o << 1, l, mid);
  else
    change(o << 1 | 1, mid + 1, r);
  up(o);
}
void Mark(int o, int l, int r) {
  if (y_1 <= l && r <= y_2)
    mark[o] ^= 1;
  else {
    int mid = l + r >> 1;
    if (y_1 <= mid) Mark(o << 1, l, mid);
    if (y_2 > mid) Mark(o << 1 | 1, mid + 1, r);
    up(o);
  }
}
node query(int o, int l, int r, bool mk) {
  mk ^= mark[o];
  if (y_1 <= l && r <= y_2)
    return mk ? res(Mi[o]) : Mx[o];
  else {
    int mid = l + r >> 1;
    if (y_2 <= mid) return query(o << 1, l, mid, mk);
    if (y_1 > mid) return query(o << 1 | 1, mid + 1, r, mk);
    return meg(query(o << 1, l, mid, mk), query(o << 1 | 1, mid + 1, r, mk));
  }
}
int n, m;
void change(int x, int k) {
  y_1 = x, ad_v = k;
  change(1, 1, n);
}
pair<int, int> que[100];
int ask(int l, int r, int k) {
  int td = 0, ans = 0;
  while (k--) {
    y_1 = l, y_2 = r;
    node now = query(1, 1, n, 0);
    if (now.Max < 0) break;
    ans += now.Max;
    y_1 = now.L, y_2 = now.R;
    Mark(1, 1, n);
    que[++td] = {now.L, now.R};
  }
  for (int q = td, q_end_ = 1; q >= q_end_; --q) {
    y_1 = que[q].first, y_2 = que[q].second;
    Mark(1, 1, n);
  }
  return ans;
}
int main() {
  read(n);
  for (int q = 1, q_end_ = n; q <= q_end_; ++q) read(val[q]);
  build(1, 1, n);
  read(m);
  int ty, l, r, k;
  while (m--) {
    read(ty);
    if (!ty) {
      read(l), read(k);
      change(l, k);
    } else {
      read(l), read(r), read(k);
      printf("%d\n", ask(l, r, k));
    }
  }
  return 0;
}
