GSS1 BUG IS ALIVE :P

#include<iostream>
#include<cstring>
using namespace std;
typedef int LL;
int B[1000000];//Debugging stuff
int E[1000000];//Debugging stuff
struct range
{
    LL sum,sumhi,sumlo,limhi,limlo,tot;
    bool imp;
    range(LL _sum=0,LL _sumhi=0,LL _sumlo=0,LL _tot=0,bool _imp = false)
    {
        tot=_tot;imp=_imp;
        sumhi=_sumhi;sumlo=_sumlo;
        sum=_sum;
    }
};
LL arr[50000];
int n;
range tree[1000000];
void fill(int node = 1, int b = 0, int e = n-1)
{
    if(b==e)
    {
        tree[node].sumhi=arr[b];
        tree[node].sumlo=arr[b];
        tree[node].sum=arr[b];   //this 4 are for assigning a leaf to SEGMENT TREE
        tree[node].tot=arr[b];
        B[node]=E[node]=b; //Debugging stuff
    }
    else
    {
        fill(2*node,b,(b+e)/2);// fill childs first
        fill(2*node+1,(b+e)/2+1,e); // fill childs first

        range p1=tree[2*node],p2=tree[2*node+1];  //simplify use of child
        range joint;
        B[node]=b;
        E[node]=e;

        //---Here i join segment 2*node && 2*node+1 ----
        joint.tot=p1.tot+p2.tot;
        joint.sum=max(p1.sum,p2.sum);
        joint.sum=max(joint.sum,p1.sumhi+p2.sumlo);
        joint.sumhi=max(p2.sumhi,p1.sumhi+p2.tot);
        joint.sumlo=max(p1.sumlo,p2.sumlo+p1.tot);
        joint.sum=max(joint.sum,joint.sumlo);
        joint.sum=max(joint.sum,joint.sumhi);
        tree[node]=joint;
    }
}

range query(int i,int j,int node = 1, int b = 0, int e = n-1)
{
    if(j<b || e<i)
        return (-1,-1,-1,-1,true); // return imposible this child is not in query range
    if(b >=i && e<=j)
        return tree[node]; //its completely contained no need to call childs so return [node]

    range p1 = query(i,j,2*node,b,(b+e)/2); // call childs
    range p2 = query(i,j,2*node+1,(b+e)/2+1,e);

    if(p1.imp)return p2; //if p1 is not in range return p2
    if(p2.imp)return p1; //if p2 is not in the range return p1

    //same join as up .... its always the same as the initiallize in SEGMENT TREE
    range joint;
    joint.tot=p1.tot+p2.tot;
    joint.sum=max(p1.sum,p2.sum);
    joint.sum=max(joint.sum,p1.sumhi+p2.sumlo);
    joint.sumhi=max(p2.sumhi,p1.sumhi+p2.tot);
    joint.sumlo=max(p1.sumlo,p2.sumlo+p1.tot);
    joint.sum=max(joint.sum,joint.sumlo);
    joint.sum=max(joint.sum,joint.sumhi);
    return joint;
}

main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&arr[i]);
    fill(); //fill the tree NlgN suzed tree

    //Debugging stuff----------
    for(int i=0;i<2*n;++i)
        printf("%d-%d ---> %d , ---> %d\n",B[i],E[i],tree[i].tot,tree[i].sumhi);
    //End of debugging stuf ---------

    //This part is the real part of the program
    int T;scanf("%d",&T);
    while(T--)
    {
        int st,en;scanf("%d %d",&st,&en);
        printf("%d\n",query(st-1,en-1).sumhi);
    }
}