#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007ll

struct node
{
    ll mx;
    ll tsum;
    ll psum;
    ll ssum;
};

void build(node tree[],ll arr[],ll ss,ll se,ll idx)
{
    if(ss==se)
    {
        tree[idx].mx = arr[ss];
        tree[idx].tsum = arr[ss];
        tree[idx].psum = arr[ss];
        tree[idx].ssum = arr[ss];
        return;
    }
    ll m = (ss+se)/2;
    build(tree,arr,ss,m,2*idx+1);
    build(tree,arr,m+1,se,2*idx+2);

    struct node left = tree[2*idx+1];
    struct node right = tree[2*idx+2];
    tree[idx].psum = max(left.psum,right.psum+left.tsum);
    tree[idx].ssum = max(right.ssum,left.ssum+right.tsum);
    tree[idx].tsum = left.tsum+right.tsum;
    tree[idx].mx = max((left.ssum+right.psum),max(left.mx,right.mx));

}

node query(node tree[],ll ss,ll se,ll qs,ll qe,ll idx)
{
    // cout<<ss<<" "<<se;
    if(qs<=ss && qe>=se)
    {
        return tree[idx];
    }
    else if(qs>se || qe<ss)
    {
        struct node waste;
        waste.mx = waste.tsum = waste.psum = waste.ssum = -5000000ll;
        return waste;
    }

    ll m = (ss+se)/2;
    struct node left = query(tree,ss,m,qs,qe,2*idx+1);
    struct node right = query(tree,m+1,se,qs,qe,2*idx+2);
    struct node retval;
    retval.psum = max(left.psum,right.psum+left.tsum);
    retval.ssum = max(right.ssum,left.ssum+right.tsum);
    retval.tsum = left.tsum+right.tsum;
    retval.mx = max((left.ssum+right.psum),max(left.mx,right.mx));
    return retval;
}

int main()
{

    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    ll n;
    cin>>n;
    ll arr[n];
    
    for(int i=0; i<n; i++)
        cin>>arr[i];
    
    struct node tree[4*n+1];

    for(ll i=0; i<4*n+1; i++)
    {
        tree[i].mx = -5000000ll;
        tree[i].tsum = -5000000ll;
        tree[i].psum = -5000000ll;
        tree[i].ssum = -5000000ll;        
    }
    build(tree,arr,0,n-1,1);
    // for(ll i=1; i<4*n+1; i++)
    // {
    //     cout<<tree[i].mx<<" "<<tree[i].tsum<<" "<<tree[i].psum<<" "<<tree[i].ssum<<endl;
    // }

    ll q, l, r;
    cin>>q;
    while(q--)
    {
        cin>>l;
        cin>>r;
        l--;
        r--;
        struct node ans = query(tree,0,n-1,l,r,1);
        cout<<ans.mx<<endl;
    }

    

    return 0;
}