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