GSS (Segment Tree)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 6;
const int INF = 1e9 + 7;

#define left first.first
#define right first.second
#define sum second.first
#define ans second.second

long long n, m, a[N];
typedef pair <long long, long long> ii;
typedef pair <ii, ii> iiii;
iiii st[N * 4];

void build(int id, int l, int r) {
    if (l == r) {
        st[id] = iiii (ii(a[l], a[l]), ii(a[l], a[l]) );
        return;
    }

    int mid = (l+r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1,r);

    st[id].left = max(st[id*2].left, st[id*2].sum + st[id*2+1].left);

    st[id].right = max(st[id*2+1].right, st[id*2+1].sum + st[id*2].right);

    st[id].sum = st[id*2].sum + st[id*2+1].sum;

    st[id].ans = max (max(st[id*2].ans, st[id*2+1].ans), st[id*2].right + st[id*2+1].left);
}

iiii get(int id, int l, int r, int u, int v) {
    if (v < l || r < u)
        return iiii (ii(0,-INF), ii(-INF,-INF));

    if (u <= l && r <= v)
        return st[id];

    int mid = (l+r) / 2;

    iiii t1 = get(id * 2, l, mid, u, v);
    iiii t2 = get(id * 2 + 1, mid + 1, r, u, v);

    long long left1 = max(t1.left, t1.sum + t2.left);
    long long right1 = max(t2.right, t2.sum + t1.right);
    long long sum1 = t1.sum + t2.sum;
    long long ans1 = max (max(t1.ans, t2.ans), t1.right + t2.left);

    return iiii (ii(left1, right1), ii(sum1, ans1));
}

int main()
{
    //freopen("GSS.inp","r",stdin);
    //freopen("GSS.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 1;i <= n; i++)
        cin >> a[i];

    build(1, 1, n);

    cin >> m;
    while (m--) {
        int x, y; cin >> x >> y;
        cout << get(1, 1, n, x, y).ans << '\n';
    }

    return 0;
}