#include<fstream>
#include<limits>
#define MAXN 200001
#define INF 1844674407370930
using namespace std;
typedef int64_t var;
ifstream fin("maxq.in");
ofstream fout("maxq.out");
var n, m;
struct Quad {
var b, m, e, s;
Quad(var a, var B, var c, var d) {
b = a; m = B; e = c; s = d;
}
Quad() {}
};
Quad TREE[3*MAXN];
var A[MAXN];
Quad update(Quad l, Quad r) {
Quad rez(-INF, -INF, -INF, -INF);
rez.s = l.s + r.s;
rez.b = max(l.b, r.b + l.s);
rez.e = max(r.e, l.e + r.s);
rez.m = max(l.m, r.m);
rez.m = max(rez.m, l.e+r.b);
return rez;
}
void build(var node, var b, var e) {
if(b == e) {
TREE[node] = Quad(A[b], A[b], A[b], A[b]);
} else {
var m = (b+e)/2;
build(2*node, b, m);
build(2*node+1, m+1, e);
TREE[node] = update(TREE[2*node], TREE[2*node+1]);
}
}
Quad query(var node, var b, var e, var l, var r) {
if(b>r || e<l) return Quad(-INF, -INF, -INF, -INF);
if(e<=r && b>=l) return TREE[node];
var m = (b+e)/2;
Quad q1 = query(2*node, b, m, l, r);
Quad q2 = query(2*node+1, m+1, e, l, r);
return update(q1, q2);
}
void updateVal(var node, var b, var e, var poz, var val) {
if(b == e) TREE[node] = Quad(val, val, val, val);
else {
var m = (b+e)/2;
if(m >= poz) updateVal(node*2, b, m, poz, val);
else updateVal(node*2+1, m+1, e, poz, val);
TREE[node] = update(TREE[2*node], TREE[node*2+1]);
}
}
int main() {
fin>>n;
var a, b, type;
for(var i=1; i<=n; i++) {
fin>>A[i];
}
build(1, 1, n);
fin>>m;
while(m--) {
fin>>type>>a>>b;
if(type == 0) {
a++;
updateVal(1, 1, n, a, b);
} else {
a++;
b++;
fout<<(query(1, 1, n, a, b)).m<<'\n';
}
}
return 0;
}