// 1kb 火车头已省略，MID 指 ((l+r)>>1)，read 快读已验证没有错误
const int N = 5e4 + 4;
struct STree {
  ll l, r, sum, dat, lm, rm;
} t[N * 4];
ll n, a[N], m, opt, x, y;
void pushup(ll k) {
  t[k].sum = t[k * 2].sum + t[k * 2 + 1].sum;
  t[k].lm = max(t[k * 2].lm, t[k * 2].sum + t[k * 2 + 1].lm);
  t[k].rm = max(t[k * 2 + 1].rm, t[k * 2 + 1].sum + t[k * 2].rm);
  t[k].dat =
      max(max(t[k * 2].dat, t[k * 2 + 1].dat), t[k * 2].rm + t[k * 2 + 1].lm);
  return;
}
void build(ll k, ll l, ll r) {
  t[k].l = l, t[k].r = r;
  if (l == r) {
    t[k].sum = t[k].dat = t[k].lm = t[k].rm = a[l];
    return;
  }
  build(k * 2, l, MID);
  build(k * 2 + 1, MID + 1, r);
  pushup(k);
}
void add(ll k, ll l, ll x) {
  if (t[k].l == t[k].r && t[k].l == l) {
    t[k].dat = t[k].sum = t[k].lm = t[k].rm = x;
    return;
  }
  ll mid = (t[k].l + t[k].r) >> 1;
  if (l > mid)
    add(k * 2 + 1, l, x);
  else
    add(k * 2, l, x);
  pushup(k);
  return;
}
STree ask(ll k, ll l, ll r) {
  if (t[k].l >= l && t[k].r <= r)
    return t[k];
  ll mid = (t[k].l + t[k].r) >> 1;
  if (l > mid)
    return ask(k * 2 + 1, l, r);
  else if (mid >= r)
    return ask(k * 2, l, r);
  STree ll, rr, ret;
  ll = ask(k * 2, l, r);
  rr = ask(k * 2 + 1, l, r);
  ret.dat = max(max(ll.dat, rr.dat), ll.rm + rr.lm);
  return ret;
}
int main() {
  n = read();
  F(i, 1, n) a[i] = read();
  build(1, 1, n);
  m = read();
  while (m--) {
    opt = read(), x = read(), y = read();
    if (opt == 0)
      add(1, x, y);
    else
      printf("%lld\n", ask(1, x, y).dat);
  }
  return 0;
}

RT，调一小时了，求指错或 hack。