#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 50050;

struct node {
    ll best, max, min;
    bool valid;

    node() : valid(false) { }

    node(ll value, ll sum) {
        best = value;
        min = sum - value;
        max = sum;
        valid = true;
    }
};

template<typename Node>
node join(Node&& left, Node&& right) {
    node ret;
    ret.valid = true;
    ret.best = max(max(left.best, right.best), right.max - left.min);
    ret.max = max(left.max, right.max);
    ret.min = min(left.min, right.min);
    return ret;
}

node t[4 * N];
int values[N];
ll sum[N];

void build(int i, int l, int r) {
    if (l == r) t[i] = node(values[l], sum[l]);
    else {
        build(i * 2, l, (l + r) / 2);
        build(i * 2 + 1, (l + r) / 2 + 1, r);
        t[i] = join(t[i * 2], t[i * 2 + 1]);
    }
}

node query(int i, int l, int r, int a, int b) {
    if (r < a || l > b) return node();
    else if (a <= l && b >= r) return t[i];

    auto left = query(i * 2, l, (l + r) / 2, a, b);
    auto right = query(i * 2 + 1, (l + r) / 2 + 1, r, a, b);

    if (!left.valid) return right;
    else if (!right.valid) return left;

    return join(left, right);
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", values + i);
        sum[i] += sum[i - 1] + values[i];
    }

    build(1, 1, n);

    int m;
    scanf("%d", &m);

    int l, r;
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%lld\n", query(1, 1, n, l, r).best);
    }

    return 0;
}