#include<bits/stdc++.h>
using namespace std;
#define max(a,b) a>b?a:b
struct node
{
    long long int prefix,suffix,total,maxm;
};
node segtree[4*50010];
vector<int> tree;
void build(int s,int e,int index)
{
    if(s==e)
    {
        segtree[index].prefix = segtree[index].suffix = segtree[index].total =  segtree[index].maxm = tree[s];
        return;
    }
    int mid =(s+e)/2;
    build(s,mid,2*index+1);
    build(mid+1,e,2*index+2);
    int left = 2*index+1;
    int right = 2*index+2;
    segtree[index].total = segtree[left].total+segtree[right].total;
    segtree[index].prefix = max(segtree[left].prefix,segtree[right].prefix+segtree[left].total);
    segtree[index].suffix = max(segtree[right].suffix,segtree[left].suffix+segtree[right].total);
    segtree[index].maxm = max(segtree[index].suffix,max(segtree[index].prefix,max(max(segtree[left].maxm,segtree[right].maxm),segtree[left].suffix+segtree[right].prefix)));
    return;
}

node query(int s,int e,int qs,int qe,int index)
{
    node res;
    res.prefix = res.suffix = res.maxm = res.total = LONG_MIN;
    if(e<qs || s>qe)
    {
        return res;
    }
    else if(qs<=s && qe>=e)
    {
        return segtree[index];
    }
    int l = 2*index+1;
    int r = 2*index+2;
    int mid = (s+e)/2;
    if (qs > mid)
         return query(mid+1, e, qs, qe,r);
    if (qe <= mid)
         return query(s, mid, qs, qe,l);
    node left = query(s,mid,qs,qe,l);
    node right = query(mid+1,e,qs,qe,r);
    res.total = left.total+right.total;
    res.prefix = max(left.prefix,right.prefix+left.total);
    res.suffix = max(right.suffix,left.suffix+right.total);
    res.maxm = max(res.suffix,max(res.prefix,max(max(left.maxm,right.maxm),left.suffix+right.prefix)));
    return res;
}

int main()
{
    int n;
    cin>>n;
    long long int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        tree.push_back(x);
    }
    build(0,n-1,0);
    int m;
    cin>>m;
    int s,e;
    while(m--)
    {
        cin>>s>>e;
        cout<<query(0,n-1,--s,--e,0).maxm<<endl;
    }
}