#include <cmath>
#include <cstring>
#include <vector>
#include <iostream>
 
using namespace std;
struct list
{
    long sum,bestsum,left,right;
};
 
list* make_new_node(long s,long bs,long l,long r)
{
    list* temp=new list();
    temp->sum=s;
    temp->bestsum=bs;
    temp->left=l;
    temp->right=r;
    return temp;
}
 
void build(long arr[],list* tree[],int node,int low,int high)
{
    if(low>high)
        return;
    if(low==high)
    {
        tree[node]=make_new_node(arr[low],arr[low],arr[low],arr[low]);
        return;
    }
 
    build(arr,tree,2*node+1,low,(high+low)/2);
    build(arr,tree,2*node+2,(high+low)/2+1,high);
 
//    tree[node]=NULL;
    long a=tree[2*node+1]->sum+tree[2*node+2]->sum;
    long b=max(max(tree[2*node+1]->bestsum,tree[2*node+2]->bestsum),tree[2*node+1]->right+tree[2*node+2]->left);
    long c=max(tree[2*node+1]->left,tree[2*node+1]->sum+tree[2*node+2]->left);
    long d=max(tree[2*node+1]->right+tree[2*node+2]->sum,tree[2*node+2]->right);
 
    tree[node]=make_new_node(a,b,c,d);
}
 
list* query(list* tree[],int node,int low,int high,int l,int r)
{
    if(low>high || low>r || high<l)
        return make_new_node(-15008,-15008,-15008,-15008);
    if(low>=l && high<=r)
        return tree[node];
 
    list *a=query(tree,2*node+1,low,(high+low)/2,l,r);
    list *b=query(tree,2*node+2,(high+low)/2+1,high,l,r);
 
    long w=a->sum+b->sum;
    long x=max(max(a->bestsum,b->bestsum),a->right+b->left);
    long y=max(a->left,a->sum+b->left);
    long z=max(a->right+b->sum,b->right);
    tree[node]=make_new_node(w,x,y,z);
 
    return tree[node];
}
 
int main() 
{
    //ios_base::sync_with_stdio(false);
    int n;
    scanf("%d",&n);
//    cin>>n;
    long arr[n];
    list* tree[5*n];
    for(int i=0;i<n;i++)
        scanf("%ld",&arr[i]);
//        cin>>arr[i];
    build(arr,tree,0,0,n-1);
 
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
//        cout<<query(tree,0,0,n-1,l-1,r-1)->bestsum<<endl;
        printf("%ld\n",query(tree,0,0,n-1,l-1,r-1)->bestsum);
    }
    return 0;
}
 

I2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKc3RydWN0IGxpc3QKewogICAgbG9uZyBzdW0sYmVzdHN1bSxsZWZ0LHJpZ2h0Owp9OwoKbGlzdCogbWFrZV9uZXdfbm9kZShsb25nIHMsbG9uZyBicyxsb25nIGwsbG9uZyByKQp7CiAgICBsaXN0KiB0ZW1wPW5ldyBsaXN0KCk7CiAgICB0ZW1wLT5zdW09czsKICAgIHRlbXAtPmJlc3RzdW09YnM7CiAgICB0ZW1wLT5sZWZ0PWw7CiAgICB0ZW1wLT5yaWdodD1yOwogICAgcmV0dXJuIHRlbXA7Cn0KCnZvaWQgYnVpbGQobG9uZyBhcnJbXSxsaXN0KiB0cmVlW10saW50IG5vZGUsaW50IGxvdyxpbnQgaGlnaCkKewogICAgaWYobG93PmhpZ2gpCiAgICAgICAgcmV0dXJuOwogICAgaWYobG93PT1oaWdoKQogICAgewogICAgICAgIHRyZWVbbm9kZV09bWFrZV9uZXdfbm9kZShhcnJbbG93XSxhcnJbbG93XSxhcnJbbG93XSxhcnJbbG93XSk7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgCiAgICBidWlsZChhcnIsdHJlZSwyKm5vZGUrMSxsb3csKGhpZ2grbG93KS8yKTsKICAgIGJ1aWxkKGFycix0cmVlLDIqbm9kZSsyLChoaWdoK2xvdykvMisxLGhpZ2gpOwogICAgCi8vICAgIHRyZWVbbm9kZV09TlVMTDsKICAgIGxvbmcgYT10cmVlWzIqbm9kZSsxXS0+c3VtK3RyZWVbMipub2RlKzJdLT5zdW07CiAgICBsb25nIGI9bWF4KG1heCh0cmVlWzIqbm9kZSsxXS0+YmVzdHN1bSx0cmVlWzIqbm9kZSsyXS0+YmVzdHN1bSksdHJlZVsyKm5vZGUrMV0tPnJpZ2h0K3RyZWVbMipub2RlKzJdLT5sZWZ0KTsKICAgIGxvbmcgYz1tYXgodHJlZVsyKm5vZGUrMV0tPmxlZnQsdHJlZVsyKm5vZGUrMV0tPnN1bSt0cmVlWzIqbm9kZSsyXS0+bGVmdCk7CiAgICBsb25nIGQ9bWF4KHRyZWVbMipub2RlKzFdLT5yaWdodCt0cmVlWzIqbm9kZSsyXS0+c3VtLHRyZWVbMipub2RlKzJdLT5yaWdodCk7CiAgICAKICAgIHRyZWVbbm9kZV09bWFrZV9uZXdfbm9kZShhLGIsYyxkKTsKfQoKbGlzdCogcXVlcnkobGlzdCogdHJlZVtdLGludCBub2RlLGludCBsb3csaW50IGhpZ2gsaW50IGwsaW50IHIpCnsKICAgIGlmKGxvdz5oaWdoIHx8IGxvdz5yIHx8IGhpZ2g8bCkKICAgICAgICByZXR1cm4gbWFrZV9uZXdfbm9kZSgtMTUwMDgsLTE1MDA4LC0xNTAwOCwtMTUwMDgpOwogICAgaWYobG93Pj1sICYmIGhpZ2g8PXIpCiAgICAgICAgcmV0dXJuIHRyZWVbbm9kZV07CiAgICAKICAgIGxpc3QgKmE9cXVlcnkodHJlZSwyKm5vZGUrMSxsb3csKGhpZ2grbG93KS8yLGwscik7CiAgICBsaXN0ICpiPXF1ZXJ5KHRyZWUsMipub2RlKzIsKGhpZ2grbG93KS8yKzEsaGlnaCxsLHIpOwogICAgCiAgICBsb25nIHc9YS0+c3VtK2ItPnN1bTsKICAgIGxvbmcgeD1tYXgobWF4KGEtPmJlc3RzdW0sYi0+YmVzdHN1bSksYS0+cmlnaHQrYi0+bGVmdCk7CiAgICBsb25nIHk9bWF4KGEtPmxlZnQsYS0+c3VtK2ItPmxlZnQpOwogICAgbG9uZyB6PW1heChhLT5yaWdodCtiLT5zdW0sYi0+cmlnaHQpOwogICAgdHJlZVtub2RlXT1tYWtlX25ld19ub2RlKHcseCx5LHopOwogICAgCiAgICByZXR1cm4gdHJlZVtub2RlXTsKfQoKaW50IG1haW4oKSAKewogICAgLy9pb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGludCBuOwogICAgc2NhbmYoIiVkIiwmbik7Ci8vICAgIGNpbj4+bjsKICAgIGxvbmcgYXJyW25dOwogICAgbGlzdCogdHJlZVs1Km5dOwogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICBzY2FuZigiJWxkIiwmYXJyW2ldKTsKLy8gICAgICAgIGNpbj4+YXJyW2ldOwogICAgYnVpbGQoYXJyLHRyZWUsMCwwLG4tMSk7CiAgIAogICAgaW50IHE7CiAgICBzY2FuZigiJWQiLCZxKTsKICAgIGZvcihpbnQgaT0wO2k8cTtpKyspCiAgICB7CiAgICAgICAgaW50IGwscjsKICAgICAgICBzY2FuZigiJWQlZCIsJmwsJnIpOwovLyAgICAgICAgY291dDw8cXVlcnkodHJlZSwwLDAsbi0xLGwtMSxyLTEpLT5iZXN0c3VtPDxlbmRsOwogICAgICAgIHByaW50ZigiJWxkXG4iLHF1ZXJ5KHRyZWUsMCwwLG4tMSxsLTEsci0xKS0+YmVzdHN1bSk7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=