#include<bits/stdc++.h>
using namespace std;
long long n, q, h[50005], x, y;
struct node{
    int l, r, lsum, rsum, sum, ans;
}f[200005], s;
void get(int l, int r, int id){
    f[id].l = l, f[id].r = r;
    if(l == r){
        f[id].lsum = h[l], f[id].rsum = h[l], f[id].sum = h[l], f[id].ans = h[l];
        return;
    }
    int mid = l + (r - l) / 2;
    get(l, mid, id * 2);
    get(mid + 1, r, id * 2 + 1);
    f[id].lsum = max(f[id * 2].sum + f[id * 2 + 1].lsum, f[id * 2].lsum);
    f[id].rsum = max(f[id * 2 + 1].sum + f[id * 2].rsum, f[id * 2 + 1].rsum);
    f[id].sum = f[id * 2].sum + f[id * 2 + 1].sum;
    f[id].ans = max(max(f[id * 2].ans, f[id * 2 + 1].ans), f[id * 2].rsum + f[id * 2 + 1].lsum);
}
void query(int l, int r, int id){
    if(l == f[id].l && r == f[id].r){
        s.ans = max(max(s.ans, f[id].ans), s.rsum + f[id].lsum);
        s.lsum = max(s.sum + f[id].lsum, s.lsum);
        s.rsum = max(f[id].sum + s.rsum, f[id].rsum);
        s.sum = s.sum + f[id].sum;
        return; 
    }
    if(r <= f[id * 2].r){
        query(l, r, id * 2);
    }
    else
        if(l >= f[id * 2 + 1].l)
            query(l, r, id * 2 + 1);
        else
            query(l, f[2 * id].r, id * 2), query(f[2 * id + 1].l, r, id * 2 + 1);
}
int main(){
    cin>>n;
    for(int i = 1;i <= n;i++)
        cin>>h[i];
    cin>>q;
    get(1, n, 1);
    for(int i = 1;i <= q;i++){
        cin>>x>>y;
        s.lsum = 0, s.rsum = 0, s.sum = 0, s.ans = 0;
        query(x, y, 1);
        cout<<s.ans;
        if(i < q)
            cout<<endl; 
    }
    return 0;
}