#include<cstdio>#include<iostream>#define lc k<<1#define rc k<<1|1using namespace std;const int M=1e5+5,N=M<<2;struct sgt{    int sum,gss,lgss,rgss;}tr[N];int n,m,a[N];void updata(int k){    tr[k].sum=tr[lc].sum+tr[rc].sum;    tr[k].lgss=max(tr[lc].lgss,tr[lc].sum+tr[rc].lgss);    tr[k].rgss=max(tr[rc].rgss,tr[rc].sum+tr[lc].rgss);    tr[k].gss=max(max(tr[lc].gss,tr[rc].gss),tr[lc].rgss+tr[rc].lgss);}void build(int k,int l,int r){    if(l==r){        tr[k].sum=tr[k].gss=tr[k].lgss=tr[k].rgss=a[l];        return ;    }    int mid=l+r>>1;    build(lc,l,mid);    build(rc,mid+1,r);    updata(k);}sgt query(int k,int l,int r,int x,int y){    if(l==x&&r==y) return tr[k];    int mid=l+r>>1;    if(y<=mid) return query(lc,l,mid,x,y);    else if(x>mid) return query(rc,mid+1,r,x,y);    else{        sgt left,right,result;        left=query(lc,l,mid,x,mid);        right=query(rc,mid+1,r,mid+1,y);        result.sum=left.sum+right.sum;        result.lgss=max(left.lgss,left.sum+right.lgss);        result.rgss=max(right.rgss,right.sum+left.rgss);        result.gss=max(max(left.gss,right.gss),left.rgss+right.lgss);        return result;    } }int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);    }    build(1,1,n);    scanf("%d",&m);    for(int i=1,x,y;i<=m;i++){        scanf("%d%d",&x,&y);        printf("%d\n",query(1,1,n,x,y).gss);    }    return 0;}

#include<cstdio>#include<iostream>#define lc k<<1#define rc k<<1|1using namespace std;const int M=1e5+5,N=M<<2;struct sgtment{    int sum,gss,lgss,rgss;}tr[N];int n,m,a[N];void updata(int k){    tr[k].sum=tr[lc].sum+tr[rc].sum;    tr[k].lgss=max(tr[lc].lgss,tr[lc].sum+tr[rc].lgss);    tr[k].rgss=max(tr[rc].rgss,tr[rc].sum+tr[lc].rgss);    tr[k].gss=max(max(tr[lc].gss,tr[rc].gss),tr[lc].rgss+tr[rc].lgss);}void build(int k,int l,int r){    if(l==r){        tr[k].sum=tr[k].gss=tr[k].lgss=tr[k].rgss=a[l];        return ;    }    int mid=l+r>>1;    build(lc,l,mid);    build(rc,mid+1,r);    updata(k);}void change(int k,int l,int r,int pos,int val){    if(l==r){        tr[k].sum=tr[k].gss=tr[k].lgss=tr[k].rgss=val;        return ;    }    int mid=l+r>>1;    if(pos<=mid) change(lc,l,mid,pos,val);    else change(rc,mid+1,r,pos,val);    updata(k);}sgtment query(int k,int l,int r,int x,int y){    if(l==x&&r==y) return tr[k];    int mid=l+r>>1;    if(y<=mid) return query(lc,l,mid,x,y);    else if(x>mid) return query(rc,mid+1,r,x,y);    else{        sgtment left,right,result;        left=query(lc,l,mid,x,mid);        right=query(rc,mid+1,r,mid+1,y);        result.sum=left.sum+right.sum;        result.lgss=max(left.lgss,left.sum+right.lgss);        result.rgss=max(right.rgss,right.sum+left.rgss);        result.gss=max(max(left.gss,right.gss),left.rgss+right.lgss);        return result;    } }int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);    }    build(1,1,n);    scanf("%d",&m);    for(int i=1,opt,x,y;i<=m;i++){        scanf("%d%d%d",&opt,&x,&y);        if(opt) printf("%d\n",query(1,1,n,x,y).gss);        else change(1,1,n,x,y);    }    return 0;}