#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const long long Linf = 1e18 + 5;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T lcm(T a, T b) {
  return a / __gcd(a, b) * b;
}
int read() {
  int res = 0;
  int neg;
  while (true) {
    char ch = getchar();
    if ((ch >= '0' && ch <= '9') || ch == '-') {
      if (ch == '-')
        neg = -1;
      else
        neg = 1, res = ch - '0';
      break;
    }
  }
  while (true) {
    char ch = getchar();
    if (ch >= '0' && ch <= '9')
      res *= 10, res += ch - '0';
    else
      break;
  }
  return res * neg;
}
void print(int x) {
  if (x == 0) {
    putchar('0');
    putchar('\n');
    return;
  }
  static char buf[20];
  int nn = 0;
  if (x < 0) putchar('-'), x *= -1;
  while (x) {
    buf[++nn] = x % 10 + '0';
    x /= 10;
  }
  for (int(i) = (nn); (i) >= int(1); (i)--) putchar(buf[i]);
  putchar('\n');
}
struct tree {
  int sum;
  int bestmax;
  int leftmax;
  int rightmax;
  int bestmin;
  int leftmin;
  int rightmin;
  int bestmaxLidx;
  int bestmaxRidx;
  int leftmaxLidx;
  int leftmaxRidx;
  int rightmaxLidx;
  int rightmaxRidx;
  int bestminLidx;
  int bestminRidx;
  int leftminLidx;
  int leftminRidx;
  int rightminLidx;
  int rightminRidx;
  tree(int tmp = 0, int k = 0) {
    sum = tmp;
    bestmax = max(0, tmp);
    leftmax = max(0, tmp);
    rightmax = max(0, tmp);
    bestmin = min(0, tmp);
    leftmin = min(0, tmp);
    rightmin = min(0, tmp);
    bestmaxLidx = k;
    bestmaxRidx = k;
    leftmaxLidx = k;
    leftmaxRidx = k;
    rightmaxLidx = k;
    rightmaxRidx = k;
    bestminLidx = k;
    bestminRidx = k;
    leftminLidx = k;
    leftminRidx = k;
    rightminLidx = k;
    rightminRidx = k;
  }
  tree inverse() {
    tree res;
    res.sum = -sum;
    res.bestmax = -bestmin;
    res.bestmaxLidx = bestminLidx;
    res.bestmaxRidx = bestminRidx;
    res.bestmin = -bestmax;
    res.bestminLidx = bestmaxLidx;
    res.bestminRidx = bestmaxRidx;
    res.leftmin = -leftmax;
    res.leftminLidx = leftmaxLidx;
    res.leftminRidx = leftmaxRidx;
    res.leftmax = -leftmin;
    res.leftmaxLidx = leftminLidx;
    res.leftmaxRidx = leftminRidx;
    res.rightmin = -rightmax;
    res.rightminLidx = rightmaxLidx;
    res.rightminRidx = rightmaxRidx;
    res.rightmax = -rightmin;
    res.rightmaxLidx = rightminLidx;
    res.rightmaxRidx = rightminRidx;
    return res;
  }
};
inline tree merge(const tree &a, const tree &b) {
  tree res = tree(0, 0);
  res.sum = a.sum + b.sum;
  if (res.bestmax < a.bestmax) {
    res.bestmax = a.bestmax;
    res.bestmaxLidx = a.bestmaxLidx;
    res.bestmaxRidx = a.bestmaxRidx;
  }
  if (res.bestmax < b.bestmax) {
    res.bestmax = b.bestmax;
    res.bestmaxLidx = b.bestmaxLidx;
    res.bestmaxRidx = b.bestmaxRidx;
  }
  if (res.bestmax < a.rightmax + b.leftmax) {
    res.bestmax = a.rightmax + b.leftmax;
    res.bestmaxLidx = a.rightmaxLidx;
    res.bestmaxRidx = b.leftmaxRidx;
  }
  if (res.leftmax < a.leftmax) {
    res.leftmax = a.leftmax;
    res.leftmaxLidx = a.leftmaxLidx;
    res.leftmaxRidx = a.leftmaxRidx;
  }
  if (res.leftmax < a.sum + b.leftmax) {
    res.leftmax = a.sum + b.leftmax;
    res.leftmaxLidx = a.leftmaxLidx;
    res.leftmaxRidx = b.leftmaxRidx;
  }
  if (res.rightmax < b.rightmax) {
    res.rightmax = b.rightmax;
    res.rightmaxLidx = b.rightmaxLidx;
    res.rightmaxRidx = b.rightmaxRidx;
  }
  if (res.rightmax < a.rightmax + b.sum) {
    res.rightmax = a.rightmax + b.sum;
    res.rightmaxLidx = a.rightmaxLidx;
    res.rightmaxRidx = b.rightmaxRidx;
  }
  res.bestmin = inf;
  res.leftmin = inf;
  res.rightmin = inf;
  if (res.bestmin > a.bestmin) {
    res.bestmin = a.bestmin;
    res.bestminLidx = a.bestminLidx;
    res.bestminRidx = a.bestminRidx;
  }
  if (res.bestmin > b.bestmin) {
    res.bestmin = b.bestmin;
    res.bestminLidx = b.bestminLidx;
    res.bestminRidx = b.bestminRidx;
  }
  if (res.bestmin > a.rightmin + b.leftmin) {
    res.bestmin = a.rightmin + b.leftmin;
    res.bestminLidx = a.rightminLidx;
    res.bestminRidx = b.leftminRidx;
  }
  if (res.leftmin > a.leftmin) {
    res.leftmin = a.leftmin;
    res.leftminLidx = a.leftminLidx;
    res.leftminRidx = a.leftminRidx;
  }
  if (res.leftmin > a.sum + b.leftmin) {
    res.leftmin = a.sum + b.leftmin;
    res.leftminLidx = a.leftminLidx;
    res.leftminRidx = b.leftminRidx;
  }
  if (res.rightmin > b.rightmin) {
    res.rightmin = b.rightmin;
    res.rightminLidx = b.rightminLidx;
    res.rightminRidx = b.rightminRidx;
  }
  if (res.rightmin > a.rightmin + b.sum) {
    res.rightmin = a.rightmin + b.sum;
    res.rightminLidx = a.rightminLidx;
    res.rightminRidx = b.rightminRidx;
  }
  return res;
}
const int MAXN = 1e5 + 5;
int lazy[MAXN * 5];
tree kd[MAXN * 5];
int ar[MAXN];
tree eval(int k, int b, int e) {
  if (b == e) return kd[k] = tree(ar[b], b);
  return kd[k] = merge(eval(k * 2, b, (b + e) / 2),
                       eval(k * 2 + 1, (b + e) / 2 + 1, e));
}
inline tree ret(tree kd, int lazy) {
  if (lazy & 1)
    return kd.inverse();
  else
    return kd;
}
tree find(int k, int b, int e, int x1, int x2) {
  if (b > x2 || e < x1) return tree(-inf);
  if (b >= x1 && e <= x2) return ret(kd[k], lazy[k]);
  tree L = find(k * 2, b, (b + e) / 2, x1, x2);
  tree R = find(k * 2 + 1, (b + e) / 2 + 1, e, x1, x2);
  if (L.sum == -inf) return ret(R, lazy[k]);
  if (R.sum == -inf) return ret(L, lazy[k]);
  return ret(merge(L, R), lazy[k]);
}
tree upd(int k, int b, int e, int x1, int x2) {
  if (b > x2 || e < x1) return ret(kd[k], lazy[k]);
  if (b >= x1 && e <= x2) {
    lazy[k]++;
    return ret(kd[k], lazy[k]);
  }
  tree L = upd(k * 2, b, (b + e) / 2, x1, x2);
  tree R = upd(k * 2 + 1, (b + e) / 2 + 1, e, x1, x2);
  kd[k] = merge(L, R);
  return ret(kd[k], lazy[k]);
}
tree modify(int k, int b, int e, int x, int val) {
  if (b > x || e < x) return ret(kd[k], lazy[k]);
  if (b == e) {
    kd[k] = tree(val, b);
    return ret(kd[k], lazy[k]);
  }
  kd[k] = merge(modify(k * 2, b, (b + e) / 2, x, val),
                modify(k * 2 + 1, (b + e) / 2 + 1, e, x, val));
  return ret(kd[k], lazy[k]);
}
int main() {
  int N = read();
  for (int(i) = (1); (i) <= int(N); (i)++) {
    ar[i] = read();
  }
  eval(1, 1, N);
  int M = read();
  for (int(i) = (1); (i) <= int(M); (i)++) {
    int t = read();
    if (t == 0) {
      int idx = read(), val = read();
      modify(1, 1, N, idx, val);
    } else {
      int l = read(), r = read(), k = read();
      vector<pair<int, int> > change;
      int ans = 0LL;
      for (int(j) = (1); (j) <= int(k); (j)++) {
        tree tmp = find(1, 1, N, l, r);
        if (tmp.bestmax <= 0) break;
        ans += tmp.bestmax;
        upd(1, 1, N, tmp.bestmaxLidx, tmp.bestmaxRidx);
        change.push_back(pair<int, int>(tmp.bestmaxLidx, tmp.bestmaxRidx));
      }
      for (__typeof(change.begin()) it = change.begin(); it != change.end();
           it++)
        upd(1, 1, N, it->first, it->second);
      print(ans);
    }
  }
  return 0;
}
