/*

    用线段树维护区间最长子段和，最长左子段和，最长右子段和。

*/

#include<cstdio>

#include<iostream>

#define N 50010

using namespace std;

int a[N],s[N],sum[N*],lsum[N*],rsum[N*],n,m;

void push_up(int k,int l,int r){

    int mid=l+r>>;

    lsum[k]=max(lsum[k*],s[mid]-s[l-]+lsum[k*+]);

    rsum[k]=max(rsum[k*+],rsum[k*]+s[r]-s[mid]);

    sum[k]=max(max(sum[k*],sum[k*+]),rsum[k*]+lsum[k*+]);

    sum[k]=max(max(sum[k*],sum[k*+]),rsum[k*]+lsum[k*+]);

}

void build(int l,int r,int k){

    int mid=l+r>>;

    if(l==r){

        sum[k]=lsum[k]=rsum[k]=a[l];

        return;

    }

    build(l,mid,k*);

    build(mid+,r,k*+);

    push_up(k,l,r);

}

int query_l(int l,int r,int k,int x,int y){//询问最长左子段和

    if(l==x&&r==y)return lsum[k];

    int mid=l+r>>;

    if(y<=mid) return query_l(l,mid,k*,x,y);

    else {

        return max(lsum[k*],s[mid]-s[l-]+query_l(mid+,r,k*+,mid+,y));

    }

}

int query_r(int l,int r,int k,int x,int y){//询问最长右子段和

    if(l==x&&r==y)return rsum[k];

    int mid=l+r>>;

    if(x>mid) return query_r(mid+,r,k*+,x,y);

    else {

        return max(rsum[k*+],s[r]-s[mid]+query_r(l,mid,k*,x,mid));

    }

}

int query(int l,int r,int k,int x,int y){

    if(l==x&&r==y) return sum[k];

    int mid=l+r>>;

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

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

    else {

        int ls=query_r(l,mid,k*,x,mid);

        int rs=query_l(mid+,r,k*+,mid+,y);

        return max(max(query(l,mid,k*,x,mid),query(mid+,r,k*+,mid+,y)),ls+rs);

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]),s[i]=s[i-]+a[i];

    build(,n,);

    scanf("%d",&m);

    for(int i=;i<=m;i++){

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

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

    }

    return ;

}