#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <utility>
#include <functional>
#include <valarray>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>

using namespace std;

#define REP(i, n) for(i = 0; i < (n); i++)
#define FOR(i, a, n) for(i = a; i < n; i++)
#define REV(i, a, n) for(i = a; i > n; i--)

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

typedef long long ll;
typedef long double ld;

#define MAXN 50010
#define INF 1000001000

int n, a[MAXN];
int b, c, i, m, tmp, x;

struct data {
    int sum, pref, suff, ans;
};

data t[200000];

data combine (data l, data r) {
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max (l.pref, l.sum + r.pref);
    res.suff = max (r.suff, r.sum + l.suff);
    res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
    return res;
}

data make_data (int val) {
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = max(-1000000, val);
    return res;
}

void build (int a[], int v, int tl, int tr) {
    if (tl == tr)
        t[v] = make_data(a[tl]);
    else {
        int tm = (tl + tr) / 2;
        build (a, v*2, tl, tm);
        build (a, v*2+1, tm+1, tr);
        t[v] = combine (t[v*2], t[v*2+1]);
    }
}

data query (int v, int tl, int tr, int l, int r) {
    if (l == tl && tr == r)
        return t[v];
    int tm = (tl + tr) / 2;
    if (r <= tm)
        return query (v*2, tl, tm, l, r);
    if (l > tm)
        return query (v*2+1, tm+1, tr, l, r);
    return combine (
        query (v*2, tl, tm, l, tm),
        query (v*2+1, tm+1, tr, tm+1, r)
    );
}
int main(void) {
    scanf("%d", &x);
    REP(i, x) {
        scanf("%d", &a[i+1]);
    }
    build(a, 1, 1, x+1);
    scanf("%d", &m);
    REP(i, m) {
        scanf("%d%d", &b, &c);
        printf("%d\n", query(1, 1, x+1, b, c).ans);
    }
    return 0;
}