#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define pb push_back
#define INF 100000000
#define mp make_pair
#define MOD 1000000007
#define F first
#define S second

int n;
ll a[100005];
ll total[200005];
ll ans[200005];
ll pref[200005];
ll suff[200005];

int main() {
	
	ios::sync_with_stdio(false);
    cin >> n;
    int x = 1;
    while (x < n) x *= 2;
    
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = n; i < x; i++) a[i] = -(INF*INF);
    
    n = x;
    
    for (int i = n; i < 2*n; i++) total[i] = a[i-n];
    for (int i = n-1; i > 0; i--) total[i] = total[i*2]+total[i*2+1];
    
    for (int i = n; i < 2*n; i++) pref[i] = a[i-n];
    for (int i = n-1; i > 0; i--) pref[i] = max(pref[i*2],total[i*2]+pref[i*2+1]);
    
    for (int i = n; i < 2*n; i++) suff[i] = a[i-n];
    for (int i = n-1; i > 0; i--) suff[i] = max(suff[i*2+1],total[i*2+1]+suff[i*2]);
    
    for (int i = n; i < 2*n; i++) ans[i] = a[i-n];
    for (int i = n-1; i > 0; i--) ans[i] = max(suff[i*2]+pref[i*2+1],
                                               max(ans[i*2],ans[i*2+1])
                                               );
    
    // for (int i = 0; i < 2*n; i++) cout << i << " - " << ans[i] << endl;
    
    int m;
    cin >> m;
    while (m --){
        int l,r;
        cin >> l >> r;
        l --;
        l += n;
        r += n;
        ll res = -1500000;
        while (l < r){
            if (l%2) res = max(res,ans[l++]);
            if (r%2) res = max(res,ans[--r]);
            l /= 2;
            r /= 2;
        }
        cout << res << endl;
    }
}