#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<iostream>

#define inf (1<<62)

using namespace std;

typedef long long ll;

const int maxn=;

ll a[maxn],sum[maxn<<],la[maxn<<],ra[maxn<<],gss[maxn<<];

int n;

struct node{

    ll sum,la,ra,gss;

};

void pushup(int rt){

    int l=rt<<,r=rt<<|;

    la[rt]=max(la[l],sum[l]+la[r]);

    ra[rt]=max(ra[r],sum[r]+ra[l]);

    gss[rt]=max(ra[l]+la[r],gss[l]);

    gss[rt]=max(gss[rt],gss[r]);

    sum[rt]=sum[l]+sum[r];

}

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

    if(l==r){

        la[rt]=ra[rt]=gss[rt]=sum[rt]=a[l];

        return;

    }

    int mid=(l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid+,r);

    pushup(rt);

}

//query有问题，也需要pushup

node query(int rt,int l,int r,int tl,int tr){

    if(tl<=l&&tr>=r){

        return {sum[rt],la[rt],ra[rt],gss[rt]};

    }

    int mid=(l+r)>>;

    if(tr<=mid) return query(rt<<, l, mid,tl, tr);

    if(tl>mid) return query(rt<<|, mid+, r,tl, tr);

    node lo=query(rt<<, l, mid,tl, tr),ro=query(rt<<|, mid+, r,tl, tr),ans;

    ans.sum = lo.sum + ro.sum;

    ans.gss = max(max(lo.gss, ro.gss), lo.ra + ro.la);

    ans.la = max(lo.la, lo.sum + ro.la);

    ans.ra = max(ro.ra, ro.sum + lo.ra);

    return ans;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lld",a+i);

    build(,,n);

    int q,t1,t2;

    scanf("%d",&q);

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

        scanf("%d%d",&t1,&t2);

        ll ans=query(,,n,t1,t2).gss;

        printf("%lld\n",ans);

    }

    return ;

}