#include <bits/stdc++.h>
 
typedef long long lld;
typedef unsigned long long llu;
#define rep(i,x,y)  for(i=x;i<y;i++)
#define rrep(i,x,y) for(i=x;i>=y;i--)
#define trv(y,x)    for(typeof(x.begin())y=x.begin();y!=x.end();y++)
#define MID(x,y)    (x+((y-x)/2))
using namespace std;
 
 
#define MAX (1<<16)
#define MAX2 (MAX<<2)
 
 
 
 
int A[MAX];
struct node
{
    int bestleftsum,bestrightsum,sum,bestsum;
    void Merge(node &A,node &B)
    {
        sum=A.sum+B.sum;
        bestleftsum=max(A.bestleftsum,A.sum+B.bestleftsum);
        bestrightsum=max(A.bestrightsum+B.sum,B.bestrightsum);
        bestsum=max(max(A.bestsum,B.bestsum),A.bestrightsum+B.bestleftsum);
    }
    void CreateLeaf(int val)
    {
        sum=bestleftsum=bestrightsum=bestsum=val;
    }
};
 
 
 
    node T[MAX2];
    void init(int index,int l,int r)
    {
        if(l==r)
            {
                T[index].CreateLeaf(A[l]);
                return;
            }
        else
        {
            int mid=MID(l,r);
            init(2*index,l,mid);
            init(2*index+1,mid+1,r);
            T[index].Merge(T[2*index],T[2*index+1]);
        }
 
    }
    void query(node& result,int l,int r,int u,int v,int index)
    {
        if(u==l && v==r)
            {
                result=T[index];
                return;
            }
        else
        {
           int mid=MID(l,r);
           if(mid>=v)
                query(result,l,mid,u,v,2*index);
            else if(mid<u)
                query(result,mid+1,r,u,v,2*index+1);
            else
            {
                node left,right;
                query(left,l,mid,u,mid,2*index);
                query(right,mid+1,r,mid+1,v,2*index+1);
                result.Merge(left,right);
          
          	} 
         }
    } 

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int n,t,x,y;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>A[i];
    init(1,0,n-1);
    cin>>t;
    node Ans;
    while(t--)
    {
        cin>>x>>y;
        query(Ans,0,n-1,x-1,y-1,1);
        cout<<Ans.bestsum<<"\n";
    }
 
 
 
    return 0;
}