#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define nl "\n"
#define ull unsigned long long
#define rv return void
#define str string
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define vec vector
#define fixed(n) fixed << setprecision(n)
#define Moageza ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
const ll mod = 1e9+7;
//////////////////////////////////////////////////////
struct SegmentTree{
private:
#define L 2*node+1
#define R 2*node+2
#define mid (l+r>>1)
struct Node{
    ll sum{}, ans{}, mx_pref{}, mx_suff{};
    Node() {}
    Node(ll val) {
        sum = val;
        ans = mx_pref = mx_suff = val;
};
};
Node merge(Node x, Node y){
    Node res;
      res.sum = x.sum + y.sum;
      res.ans = max({x.ans, y.ans, x.mx_suff + y.mx_pref});
      res.mx_pref = max(x.mx_pref, x.sum + y.mx_pref);
      res.mx_suff = max(y.mx_suff, y.sum + x.mx_suff);
      return res;
  }
    int sz;vector<Node>seg;
    void update(int l,int r,int node,int idx,ll val)
    {
        if(l==r)
        {
            seg[node]=Node(val);
            return;
        }
        if(idx<=mid)
        {
            update(l,mid,L,idx,val);
        }
        else
        {
            update(mid+1,r,R,idx,val);
        }
        seg[node]=merge(seg[L],seg[R]);
    }
    Node query(int l,int r,int node,int lq,int rq)
    {
        if(r<lq||l>rq)
        {
            return Node(-1e12);
        }
        if(l>=lq&&r<=rq)
        {
            return seg[node];
        }
        Node lft=query(l,mid,L,lq,rq);
        Node rgt=query(mid+1,r,R,lq,rq);
        return merge(lft,rgt);
    }
public:
    SegmentTree(int n)
    {
        sz=1;
        while(sz<n) sz*=2;
        seg=vector<Node>(sz*2);
    }
    void update(int idx,ll val)
    {
        update(0,sz-1,0,idx,val);
    }
    ll query(int l,int r)
    {
        return query(0,sz-1,0,l,r).ans;
    }
};
void solve(){
     int a,b;cin >> a;
   SegmentTree st(a);
   for(int i=0;i<a;i++){
    int x;cin >> x;
    st.update(i,x);
   }
   cin>> b;
   for(int i=0;i<b;i++){
    int x,y;cin >>x>>y;
    cout <<st.query(x-1,y-1)<<nl;
   }
}
int main()
{
   Moageza
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
    #endif
    int t = 1;
    //  cin >> t;
    while (t--) {
        solve();
        cout << nl;
    }
    return 0;
}