GSS1

#include <algorithm>
#include <cstdio>

using namespace std;

struct Node {
    int sum, leftsum, rightsum, maxsum;
};

const int N = 50005, INF = 0x3FFFFFFF;
int arr[N];
Node nodes[4*N];

void build(int i, int l, int r) {
    if (l == r) {
        nodes[i] = {arr[l], arr[l], arr[l], arr[l]};
        return;
    }
    build(2*i, l, (l+r)/2);
    build(2*i+1, (l+r)/2+1, r);
    nodes[i].sum = nodes[2*i].sum + nodes[2*i+1].sum;
    nodes[i].leftsum = max(nodes[2*i].leftsum,
                           nodes[2*i].sum + nodes[2*i+1].leftsum);
    nodes[i].rightsum = max(nodes[2*i+1].rightsum,
                            nodes[2*i+1].sum + nodes[2*i].rightsum);
    nodes[i].maxsum = max(nodes[2*i].rightsum + nodes[2*i+1].leftsum,
                          max(nodes[2*i].maxsum, nodes[2*i+1].maxsum));
}

Node query(int i, int l, int r, int a, int b) {
    if (a > r || b < l) {
        return {0, -INF, -INF, -INF};
    }
    if (a <= l && r <= b) {
        return nodes[i];
    }
    Node lnode = query(2*i, l, (l+r)/2, a, b);
    Node rnode = query(2*i+1, (l+r)/2+1, r, a, b);
    return {lnode.sum + rnode.sum,
            max(lnode.leftsum, lnode.sum + rnode.leftsum),
            max(rnode.rightsum, rnode.sum + lnode.rightsum),
            max(lnode.rightsum + rnode.leftsum,
                max(lnode.maxsum, rnode.maxsum))};
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    build(1, 1, n);
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", query(1, 1, n, a, b).maxsum);
    }
}