#include <bits/stdc++.h>
using namespace std;
const int maxn = 1E5 + 5;
int n, m, a[maxn];
bool tag[maxn * 4];
int waitL[55], waitR[55];
struct node {
  int maxL, maxR, minL, minR, minAns, maxAns, sum, l, r;
  int pmaxL, pmaxR, pminL, pminR, pminAnsL, pminAnsR, pmaxAnsL, pmaxAnsR;
  node(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0,
       int g = 0, int h = 0, int i = 0, bool flag = 0) {
    maxL = a, maxR = b, minL = c, minR = d, minAns = e, maxAns = f, sum = g,
    l = h, r = i;
  }
  node operator*(const node& A) {
    node B(maxL, A.maxR, minL, A.minR, min(minAns, A.minAns),
           max(maxAns, A.maxAns), sum + A.sum, l, A.r);
    B.pmaxL = pmaxL, B.pmaxR = A.pmaxR;
    B.pminL = pminL, B.pminR = A.pminR;
    if (minAns <= A.minAns)
      B.pminAnsL = pminAnsL, B.pminAnsR = pminAnsR;
    else
      B.pminAnsL = A.pminAnsL, B.pminAnsR = A.pminAnsR;
    if (maxAns >= A.maxAns)
      B.pmaxAnsL = pmaxAnsL, B.pmaxAnsR = pmaxAnsR;
    else
      B.pmaxAnsL = A.pmaxAnsL, B.pmaxAnsR = A.pmaxAnsR;
    if (sum + A.maxL > B.maxL) B.pmaxL = A.pmaxL;
    B.maxL = max(B.maxL, sum + A.maxL);
    if (maxR + A.sum > B.maxR) B.pmaxR = pmaxR;
    B.maxR = max(B.maxR, maxR + A.sum);
    if (sum + A.minL < B.minL) B.pminL = A.pminL;
    B.minL = min(B.minL, sum + A.minL);
    if (minR + A.sum < B.minR) B.pminR = pminR;
    B.minR = min(B.minR, minR + A.sum);
    B.minAns = min(B.minAns, min(B.minL, min(B.minR, minR + A.minL)));
    B.maxAns = max(B.maxAns, max(B.maxL, max(B.maxR, maxR + A.maxL)));
    if (B.minL == B.minAns)
      B.pminAnsL = B.l, B.pminAnsR = B.pminL;
    else if (B.minR == B.minAns)
      B.pminAnsL = B.pminR, B.pminAnsR = B.r;
    else if (minR + A.minL == B.minAns)
      B.pminAnsL = pminR, B.pminAnsR = A.pminL;
    if (B.maxL == B.maxAns)
      B.pmaxAnsL = B.l, B.pmaxAnsR = B.pmaxL;
    else if (B.maxR == B.maxAns)
      B.pmaxAnsL = B.pmaxR, B.pmaxAnsR = B.r;
    else if (maxR + A.maxL == B.maxAns)
      B.pmaxAnsL = pmaxR, B.pmaxAnsR = A.pmaxL;
    return B;
  }
  void change() {
    maxL = -maxL, minL = -minL;
    swap(maxL, minL);
    maxR = -maxR, minR = -minR;
    swap(maxR, minR);
    minAns = -minAns, maxAns = -maxAns;
    swap(minAns, maxAns);
    sum = -sum;
    swap(pmaxL, pminL);
    swap(pmaxR, pminR);
    swap(pminAnsL, pmaxAnsL);
    swap(pminAnsR, pmaxAnsR);
  }
} t[maxn * 4];
void pushdown(int l, int r, int num) {
  if (!tag[num]) return;
  if (l != r) tag[num << 1] ^= 1, tag[num << 1 | 1] ^= 1;
  tag[num] = 0;
  t[num].change();
}
void update(int l, int r, int num) {
  pushdown(l, r, num);
  if (l == r) return;
  int mid = (l + r) >> 1;
  pushdown(l, mid, num << 1), pushdown(mid + 1, r, num << 1 | 1);
  t[num] = t[num << 1] * t[num << 1 | 1];
}
void build(int l, int r, int num) {
  if (l == r) {
    t[num] = node(a[l], a[l], a[l], a[l], a[l], a[l], a[l], l, r, 1);
    t[num].pmaxL = t[num].pmaxR = t[num].pminL = t[num].pminR =
        t[num].pminAnsL = t[num].pminAnsR = t[num].pmaxAnsL = t[num].pmaxAnsR =
            l;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, num << 1), build(mid + 1, r, num << 1 | 1);
  t[num] = t[num << 1] * t[num << 1 | 1];
}
node ask(int L, int R, int l, int r, int num) {
  update(l, r, num);
  if (L <= l && r <= R) return t[num];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return ask(L, R, l, mid, num << 1);
  else if (mid < L)
    return ask(L, R, mid + 1, r, num << 1 | 1);
  else {
    node A = ask(L, R, l, mid, num << 1),
         B = ask(L, R, mid + 1, r, num << 1 | 1);
    return A * B;
  }
}
void flip(int L, int R, int l, int r, int num) {
  if (L <= l && r <= R) {
    tag[num] ^= 1;
    update(l, r, num);
    return;
  }
  update(l, r, num);
  int mid = (l + r) >> 1;
  if (R <= mid)
    flip(L, R, l, mid, num << 1);
  else if (mid < L)
    flip(L, R, mid + 1, r, num << 1 | 1);
  else
    flip(L, R, l, mid, num << 1), flip(L, R, mid + 1, r, num << 1 | 1);
  update(l, r, num);
}
void change(int l, int r, int pos, int x, int num) {
  update(l, r, num);
  if (l == r) {
    t[num] = node(x, x, x, x, x, x, x, l, r);
    t[num].pmaxL = t[num].pmaxR = t[num].pminL = t[num].pminR =
        t[num].pminAnsL = t[num].pminAnsR = t[num].pmaxAnsL = t[num].pmaxAnsR =
            l;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    change(l, mid, pos, x, num << 1);
  else
    change(mid + 1, r, pos, x, num << 1 | 1);
  update(l, r, num);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  build(1, n, 1);
  cin >> m;
  while (m--) {
    int opt, l, r, k;
    cin >> opt;
    if (opt == 1) {
      cin >> l >> r >> k;
      int sum = 0, ans = 0;
      for (int i = 1; i <= k; ++i) {
        node A = ask(l, r, 1, n, 1);
        sum += A.maxAns;
        waitL[i] = A.pmaxAnsL, waitR[i] = A.pmaxAnsR;
        flip(waitL[i], waitR[i], 1, n, 1);
        ans = max(ans, sum);
      }
      for (int i = k; i >= 1; --i) flip(waitL[i], waitR[i], 1, n, 1);
      cout << ans << endl;
    } else {
      cin >> l >> k;
      change(1, n, l, k, 1);
    }
  }
  return 0;
}
