#include<cstdio>

#include<iostream>

#define lc k<<1

#define rc k<<1|1

using namespace std;

const int M=1e5+,N=M<<;

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>>;

    build(lc,l,mid);

    build(rc,mid+,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>>;

    if(y<=mid) return query(lc,l,mid,x,y);

    else if(x>mid) return query(rc,mid+,r,x,y);

    else{

        sgt left,right,result;

        left=query(lc,l,mid,x,mid);

        right=query(rc,mid+,r,mid+,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=;i<=n;i++){

        scanf("%d",&a[i]);

    }

    build(,,n);

    scanf("%d",&m);

    for(int i=,x,y;i<=m;i++){

        scanf("%d%d",&x,&y);

        printf("%d\n",query(,,n,x,y).gss);

    }

    return ;

}

#include<cstdio>

#include<iostream>

#define lc k<<1

#define rc k<<1|1

using namespace std;

const int M=1e5+,N=M<<;

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>>;

    build(lc,l,mid);

    build(rc,mid+,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>>;

    if(pos<=mid) change(lc,l,mid,pos,val);

    else change(rc,mid+,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>>;

    if(y<=mid) return query(lc,l,mid,x,y);

    else if(x>mid) return query(rc,mid+,r,x,y);

    else{

        sgtment left,right,result;

        left=query(lc,l,mid,x,mid);

        right=query(rc,mid+,r,mid+,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=;i<=n;i++){

        scanf("%d",&a[i]);

    }

    build(,,n);

    scanf("%d",&m);

    for(int i=,opt,x,y;i<=m;i++){

        scanf("%d%d%d",&opt,&x,&y);

        if(opt) printf("%d\n",query(,,n,x,y).gss);

        else change(,,n,x,y);

    }

    return ;

}