#include <bits/stdc++.h>
using namespace std;
bool cur1;
int A[100005];
void check_min(int &x, int y) {
  if (x > y) x = y;
}
void check_max(int &x, int y) {
  if (x < y) x = y;
}
struct node {
  int sum;
  int mx, L, R;
  int mxL, ToL, mxR, ToR;
  void Init(int d, int x) {
    sum = d;
    mx = d;
    mxL = d;
    mxR = d;
    L = x, R = x, ToL = x, ToR = x;
  }
  node operator+(const node &_) const {
    node res;
    res.sum = sum + _.sum;
    res.mx = max(mx, _.mx);
    if (mx == res.mx)
      res.L = L, res.R = R;
    else
      res.L = _.L, res.R = _.R;
    if (mxR + _.mxL > res.mx) {
      res.mx = mxR + _.mxL;
      res.L = ToR;
      res.R = _.ToL;
    }
    res.mxL = mxL;
    res.ToL = ToL;
    if (sum + _.mxL > res.mxL) {
      res.mxL = sum + _.mxL;
      res.ToL = _.ToL;
    }
    res.mxR = _.mxR;
    res.ToR = _.ToR;
    if (_.sum + mxR > res.mxR) {
      res.mxR = _.sum + mxR;
      res.ToR = ToR;
    }
    return res;
  }
  void Print() {
    printf("sum=%d\n", sum);
    printf("res=%d [%d %d]\n", mx, L, R);
    printf("sumL=%d ToL=%d\n", mxL, ToL);
    printf("sumR=%d ToR=%d\n", mxR, ToR);
  }
};
struct Segment_tree {
  struct tree_node {
    int L, R;
    node val1, val2;
    bool Lazy;
    void Reverse() {
      Lazy = !Lazy;
      swap(val1, val2);
    }
    tree_node operator+(const tree_node &_) const {
      tree_node res;
      res.L = L;
      res.R = _.R;
      res.val1 = val1 + _.val1;
      res.val2 = val2 + _.val2;
      return res;
    }
  } tree[100005 << 2];
  int Pc[100005];
  void Up(int p) {
    tree[p].val1 = tree[p << 1].val1 + tree[p << 1 | 1].val1;
    tree[p].val2 = tree[p << 1].val2 + tree[p << 1 | 1].val2;
  }
  void Down(int p) {
    if (!tree[p].Lazy) return;
    tree[p << 1].Reverse();
    tree[p << 1 | 1].Reverse();
    tree[p].Lazy = false;
  }
  void Build(int L, int R, int p) {
    tree[p].L = L, tree[p].R = R;
    tree[p].Lazy = false;
    if (L == R) {
      Pc[L] = p;
      tree[p].val1.Init(A[L], L);
      tree[p].val2.Init(-A[L], L);
      return;
    }
    int mid = (L + R) >> 1;
    Build(L, mid, p << 1);
    Build(mid + 1, R, p << 1 | 1);
    Up(p);
  }
  void Change(int L, int R, int p) {
    if (L <= tree[p].L && tree[p].R <= R) {
      tree[p].Reverse();
      return;
    }
    Down(p);
    int mid = (tree[p].L + tree[p].R) >> 1;
    if (R <= mid)
      Change(L, R, p << 1);
    else if (L > mid)
      Change(L, R, p << 1 | 1);
    else
      Change(L, mid, p << 1), Change(mid + 1, R, p << 1 | 1);
    Up(p);
  }
  tree_node Query(int L, int R, int p) {
    if (L <= tree[p].L && tree[p].R <= R) return tree[p];
    Down(p);
    int mid = (tree[p].L + tree[p].R) >> 1;
    if (R <= mid)
      return Query(L, R, p << 1);
    else if (L > mid)
      return Query(L, R, p << 1 | 1);
    else
      return Query(L, mid, p << 1) + Query(mid + 1, R, p << 1 | 1);
  }
  int STK[100005];
  void Updata(int x) {
    int p = Pc[x], top = 0;
    while (p) {
      STK[++top] = p;
      p >>= 1;
    }
    for (int i = top; i >= 2; i--) Down(STK[i]);
    tree[Pc[x]].val1.Init(A[x], x);
    tree[Pc[x]].val2.Init(-A[x], x);
    for (int i = 2; i <= top; i++) Up(STK[i]);
  }
} ST;
int stk[100005][2];
bool cur2;
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  ST.Build(1, n, 1);
  scanf("%d", &m);
  while (m--) {
    int op;
    scanf("%d", &op);
    if (op == 0) {
      int x, d;
      scanf("%d%d", &x, &d);
      A[x] = d;
      ST.Updata(x);
    } else {
      int L, R, K;
      scanf("%d%d%d", &L, &R, &K);
      int ans = 0, top = 0;
      while (K--) {
        node res = ST.Query(L, R, 1).val1;
        if (res.mx < 0) break;
        ans += res.mx;
        ST.Change(res.L, res.R, 1);
        top++;
        stk[top][0] = res.L, stk[top][1] = res.R;
      }
      while (top) ST.Change(stk[top][0], stk[top][1], 1), top--;
      printf("%d\n", ans);
    }
  }
  return 0;
}
