#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <complex>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

#define all(x) (x).begin(), (x).end()
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

#ifdef KAZAR
    #define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
    #define eprintf(...) 0
#endif

using namespace std;

template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}

typedef long long ll;
typedef pair<int, int> ii;

const int inf = 1e9 + 143;
const ll longinf = 1e18 + 143;

inline int read(){int x;scanf(" %d",&x);return x;}

const int N = 50500;
const int M = 1e6 + 100;
const int BLOCK = 400;

int a[N];
int ps[N];

int l[M], r[M];
int ans[M];

vector<int> q[N / BLOCK + 5];

bool byr(const int &a,const int &b){
    return r[a] < r[b];
}

int main(){

#ifdef KAZAR
    freopen("f.input","r",stdin);
    freopen("f.output","w",stdout);
    freopen("error","w",stderr);
#endif

    int n = read();

    for(int i = 0; i < n; i++){
        a[i] = read();
        ps[i] = ps[i - 1] + a[i];
    }

    int m = read();

    for(int i = 0; i < m; i++){
        l[i] = read() - 1;
        r[i] = read() - 1;
        ans[i] = -inf;
        q[l[i] / BLOCK].push_back(i);
    }

    for(int it = 0; it * BLOCK < n; it++){
        int from = it * BLOCK;
        int to = from + BLOCK - 1;
        sort(all(q[it]), byr);
        int ptr = to + 1, max_ps = -inf, min_ps = ps[to], max_sum = -inf;
        foreach(qit, q[it]){
            int id = *qit;
            int r = ::r[id];
            int l = ::l[id];
            if(r <= to){
                int lval = ps[l - 1];
                for(int j = l; j <= r; j++){
                    umax(ans[id], ps[j] - lval);
                    umin(lval, ps[j]);
                }
            }else{
                while(ptr <= r){
                    umax(max_sum, ps[ptr] - min_ps);
                    umax(max_ps, ps[ptr]);
                    umin(min_ps, ps[ptr]);
                    ptr++;
                }
                int lval = ps[l - 1];
                for(int i = l; i <= to; i++){
                    umax(ans[id], ps[i] - lval);
                    umin(lval, ps[i]);
                }
                umax(ans[id], max_ps - lval);
                umax(ans[id], max_sum);
            }
        }
    }

    for(int i = 0; i < m; i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}