#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
#define ll long long
#define ull unsigned long long
#define el putchar('\n')
#define sp putchar(' ')
#ifndef ONLINE_JUDGE
#  define bug(x) cerr<<"[Debug] "<<__LINE__<<":"<<#x<<"="<<(x)<<endl
#  define del cerr<<endl
#else
#  define bug(x)
#  define del
#endif
#define lc (p << 1)
#define rc (p << 1 | 1)
using namespace std;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 5e4 + 10;
int n, m;
int a[N];
struct node {
    int maxn, val, prefix, suffix;
    node operator + (const node& x) {
        node res;
        res.val = val + x.val;
        res.prefix = max(prefix, val + x.prefix);
        res.suffix = max(suffix, x.val + suffix);
        res.maxn = max({maxn, x.maxn, suffix + x.prefix});
        return res;
    }
}t[N * 4];
struct tree {
    void pushup(int p) {
        t[p] = t[lc] + t[rc];
    }
    void build(int p, int l, int r) {
        if (l == r) {
            t[p].maxn = t[p].prefix = t[p].suffix = t[p].val = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        pushup(p);
    }
    node query(int p, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return t[p];
        }
        int mid = (l + r) >> 1;
        if (x >= mid+1) {
            return query(rc, mid + 1, r, x, y);
        } if (y <= mid) {
            return query(lc, l, mid, x, y);
        } else {
            return query(lc, l, mid, x, y) + query(rc, mid + 1, r, x, y);
        }
    }
}sgt;
signed main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    sgt.build(1, 1, n);
    m = read();
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        cout << sgt.query(1, 1, n, l, r).maxn << endl;
    }
    return 0;
}