GSS1 solution

#include <bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define lol         1000000007
#define endl        '\n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define SIZE        50000
using namespace std;



void MOD(ll &x)
{
    if (x >= lol) x -= lol;
    if (x < 0) x += lol;
}



struct segtree
{
    ll maxsubsum;
    ll sum;
    ll maxprefsum;
    ll maxsufsum;
};
                                    //////////////////////////////////////
ll arr[SIZE+5];
segtree tree[4*SIZE+5];     //arr and tree are both 1-indexed//
int n, q;                           //////////////////////////////////////




void build(int node, int start, int end)
{
    if(start==end)
    {
        tree[node].maxsubsum = arr[start];
        tree[node].sum = arr[start];
        tree[node].maxprefsum = arr[start];
        tree[node].maxsufsum = arr[start];
    }
    else
    {
        int mid = (start+end)/2;
        build(2*node, start, mid);
        build(2*node+1, mid+1, end);

        //tree[node].sum=tree[node].maxprefsum=LLONG_MIN;
        //tree[node].maxsufsum=tree[node].maxsubsum=LLONG_MIN;

        tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
        tree[node].maxprefsum = max(tree[2*node].maxprefsum, tree[2*node].sum + tree[2*node+1].maxprefsum);
        tree[node].maxsufsum = max(tree[2*node+1].maxsufsum, tree[2*node+1].sum + tree[2*node].maxsufsum);
        tree[node].maxsubsum = max(tree[2*node].maxsubsum , max(tree[2*node+1].maxsubsum, tree[2*node].maxsufsum + tree[2*node+1].maxprefsum));         //CHANGES ACCORDING TO QUERY
    }
}






segtree query(int node, int start, int end, int l, int r)
{
    segtree result;
    result.sum=result.maxprefsum=LLONG_MIN;
    result.maxsufsum=result.maxsubsum=LLONG_MIN;
    if(r<start || end<l)        //range of node is completely outside given range
    {
        return result;
    }
    if(l<=start && end<=r)      // range of node is completely inside given range
    {
        return tree[node];
    }

    int mid = (start+end)/2;        //range of node is partially inside and partially outside the given range

    if (l > mid)
      return query(2*node+1, mid+1, end, l, r);
    if (r <= mid)
      return query(2*node, start, mid, l, r);


    segtree p1 = query(2*node, start, mid, l, r);
    segtree p2 = query(2*node+1, mid+1, end, l, r);

    result.sum = p1.sum + p2.sum;
    result.maxprefsum = max(p1.maxprefsum, p1.sum + p2.maxprefsum);
    result.maxsufsum = max(p2.maxsufsum, p2.sum + p1.maxsufsum);
    result.maxsubsum = max(p1.maxsubsum , max(p2.maxsubsum, p1.maxsufsum + p2.maxprefsum));         //CHANGES ACCORDING TO QUERY

    return result;          //CHANGES ACCORDING TO QUERY
}





void solve()
{
    cin>>n;
    rep(i,1,n+1)
    {
        cin>>arr[i];
    }
    build(1,1,n);
    cin>>q;
    rep(i,1,q+1)
    {
        int x, y;
        cin>>x>>y;
        segtree ans = query(1,1,n,x,y);
        cout<<ans.maxsubsum<<endl;
    }

}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}