#include <bits/stdc++.h>
#pragma comment(linker, "/stack:16777216")
using namespace std;
const int INF = 1 << 30;
const int MAX = 1 << 17;
const int ADD = 400000;
int n, m;
int A[MAX];
pair<int, int> P[MAX * 5][2][3];
int V[MAX * 5][2][3];
int S[MAX * 5];
bool B[MAX * 5];
vector<int> I;
vector<pair<int, int> > LR;
void Push(int v) {
  if (!B[v]) return;
  B[v] = 0;
  B[v * 2] ^= 1;
  B[v * 2 + 1] ^= 1;
  S[v] *= -1;
  for (int i = (0); i < (3); ++i) {
    V[v][0][i] *= -1;
    V[v][1][i] *= -1;
    swap(V[v][0][i], V[v][1][i]);
    swap(P[v][0][i], P[v][1][i]);
  }
}
void Update(int i, int l, int r, int tl, int tr) {
  S[i] = S[l] + S[r];
  V[i][0][0] = V[l][0][0], P[i][0][0] = P[l][0][0];
  if (V[r][0][0] < V[l][0][0]) V[i][0][0] = V[r][0][0], P[i][0][0] = P[r][0][0];
  V[i][1][0] = V[l][1][0], P[i][1][0] = P[l][1][0];
  if (V[r][1][0] > V[l][1][0]) V[i][1][0] = V[r][1][0], P[i][1][0] = P[r][1][0];
  if (P[l][0][2].first <= P[l][0][2].second ||
      P[r][0][1].first <= P[r][0][1].second)
    if (V[l][0][2] + V[r][0][1] < V[i][0][0])
      V[i][0][0] = V[l][0][2] + V[r][0][1],
      P[i][0][0] = make_pair(P[l][0][2].first, P[r][0][1].second);
  if (P[l][1][2].first <= P[l][1][2].second ||
      P[r][1][1].first <= P[r][1][1].second)
    if (V[l][1][2] + V[r][1][1] > V[i][1][0])
      V[i][1][0] = V[l][1][2] + V[r][1][1],
      P[i][1][0] = make_pair(P[l][1][2].first, P[r][1][1].second);
  V[i][0][1] = V[l][0][1], P[i][0][1] = P[l][0][1];
  if (V[r][0][1] + S[l] < V[i][0][1])
    V[i][0][1] = V[r][0][1] + S[l],
    P[i][0][1] = make_pair(tl, P[r][0][1].second);
  V[i][1][1] = V[l][1][1], P[i][1][1] = P[l][1][1];
  if (V[r][1][1] + S[l] > V[i][1][1])
    V[i][1][1] = V[r][1][1] + S[l],
    P[i][1][1] = make_pair(tl, P[r][1][1].second);
  V[i][0][2] = V[r][0][2], P[i][0][2] = P[r][0][2];
  if (V[l][0][2] + S[r] < V[i][0][2])
    V[i][0][2] = V[l][0][2] + S[r],
    P[i][0][2] = make_pair(P[l][0][2].first, tr);
  V[i][1][2] = V[r][1][2], P[i][1][2] = P[r][1][2];
  if (V[l][1][2] + S[r] > V[i][1][2])
    V[i][1][2] = V[l][1][2] + S[r],
    P[i][1][2] = make_pair(P[l][1][2].first, tr);
}
void Flip(int l, int r, int i, int tl, int tr) {
  Push(i);
  if (l == tl && r == tr) {
    B[i] = 1;
    Push(i);
  } else {
    int mid = (tl + tr) / 2;
    Push(i * 2);
    Push(i * 2 + 1);
    if (r <= mid)
      Flip(l, r, i * 2, tl, mid);
    else if (l > mid)
      Flip(l, r, i * 2 + 1, mid + 1, tr);
    else {
      Flip(l, mid, i * 2, tl, mid);
      Flip(mid + 1, r, i * 2 + 1, mid + 1, tr);
    }
    Update(i, i * 2, i * 2 + 1, tl, tr);
  }
}
void Change(int j, int d, int i, int l, int r) {
  Push(i);
  if (l == r) {
    S[i] = d;
    V[i][0][0] = V[i][1][0] = d;
    P[i][0][0] = P[i][1][0] = make_pair(l, r);
    P[i][0][1] = P[i][1][1] = make_pair(l, l - 1);
    P[i][0][2] = P[i][0][2] = make_pair(l, l + 1);
    V[i][0][1] = V[i][1][1] = V[i][0][2] = V[i][1][2] = 0;
    if (d < 0) {
      V[i][0][1] = V[i][0][2] = d;
      P[i][0][1] = P[i][0][2] = make_pair(l, l);
    }
    if (d > 0) {
      V[i][1][1] = V[i][1][2] = d;
      P[i][1][1] = P[i][1][2] = make_pair(l, l);
    }
  } else {
    Push(i * 2);
    Push(i * 2 + 1);
    int mid = (l + r) / 2;
    if (j <= mid)
      Change(j, d, i * 2, l, mid);
    else
      Change(j, d, i * 2 + 1, mid + 1, r);
    Update(i, i * 2, i * 2 + 1, l, r);
  }
}
void Get(int l, int r, int i, int tl, int tr) {
  Push(i);
  if (l == tl && r == tr) {
    LR.push_back(make_pair(l, r));
    I.push_back(i);
    return;
  }
  Push(i * 2);
  Push(i * 2 + 1);
  int mid = (tl + tr) / 2;
  if (r <= mid)
    Get(l, r, i * 2, tl, mid);
  else if (l > mid)
    Get(l, r, i * 2 + 1, mid + 1, tr);
  else {
    Get(l, mid, i * 2, tl, mid);
    Get(mid + 1, r, i * 2 + 1, mid + 1, tr);
  }
}
pair<int, pair<int, int> > Get(int l, int r) {
  I.clear();
  LR.clear();
  Get(l, r, 1, 0, n - 1);
  for (int i = (0); i < (2); ++i)
    for (int j = (0); j < (3); ++j) {
      S[ADD] = S[I[0]];
      V[ADD][i][j] = V[I[0]][i][j];
      P[ADD][i][j] = P[I[0]][i][j];
    }
  for (int i = (1); i < (I.size()); ++i)
    Update(ADD + i, ADD + i - 1, I[i], LR[0].first, LR[i].second);
  int id = ADD + I.size() - 1;
  return make_pair(V[id][1][0], P[id][1][0]);
}
int main() {
  cin >> n;
  for (int i = (0); i < (n); ++i) {
    scanf("%d", &A[i]);
    Change(i, A[i], 1, 0, n - 1);
  }
  cin >> m;
  for (int i = (0); i < (m); ++i) {
    int q;
    scanf("%d", &q);
    if (q == 0) {
      int pos, val;
      scanf("%d %d", &pos, &val);
      Change(pos - 1, val, 1, 0, n - 1);
    } else {
      int l, r, k;
      scanf("%d %d %d", &l, &r, &k);
      --l;
      --r;
      int res = 0;
      vector<pair<int, int> > F;
      for (int it = (0); it < (k); ++it) {
        pair<int, pair<int, int> > t;
        t = Get(l, r);
        if (t.first <= 0) break;
        res += t.first;
        Flip(t.second.first, t.second.second, 1, 0, n - 1);
        F.push_back(make_pair(t.second.first, t.second.second));
      }
      for (int it = (0); it < (F.size()); ++it)
        Flip(F[it].first, F[it].second, 1, 0, n - 1);
      printf("%d\n", res);
    }
  }
  return 0;
}
