#include <bits/stdc++.h>
    using namespace std;
     
    typedef 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() {
    	
    	freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_gss1.txt", "r", stdin);
     
    	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);
     
        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 --){
            ll l,r;
            cin >> l >> r;
            l --;
            l += n;
            r += n;
            ll res = -(INF);
            ll prev = res;
            long R1[100005], R2[100005], r1=0, r2=0;
     
            while (l < r){
                if (l%2 == 1){
                    // res = max(res,ans[l++]);
                    l++;
                    R1[r1++] = l-1;
                }
                if (r%2 == 1){
                    // res = max(res,ans[--r]);
                    --r;
                    R2[r2++] = r;
                }
     
                // cout << l << " " << r << " " << res << endl;
     
                l /= 2;
                r /= 2;
            }
     
            for (long i = r2-1; i >= 0; i --) R1[r1++] = R2[i];
     
            for (long i = 0; i < r1; i++){
                res = max(res,ans[R1[i]]);
                res = max(res,prev+pref[R1[i]]);
                prev = max(prev+total[R1[i]],suff[R1[i]]);
            }
     
            cout << res << endl;
        }
    }