Hello there i'm starting to learn about segment tree and its applications i came across this problem and found very interesting and although i am sure of my solution it keeps getting WA here's the problem

and here is the code

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

const long long mod = 1e9 + 7;
const double eps = 1e-18;
const double PI = atan(1.0);
#define readFile freopen("input","r",stdin);
#define writeFile freopen("output","w",stdout);
#define fastIO ios::sync_with_stdio(0);
typedef unsigned long long ULL;
typedef pair<int,int> ii;


struct Node{
    int sum,ls,rs,best;
    Node(){}
    Node(int sum,int ls,int rs,int best){
        this->sum = sum;
        this->ls = ls;
        this->rs = rs;
        this->best = best;
    }
};

Node merge(Node n1,Node n2){
    int sum,ls,rs,best;
    sum = n1.sum+n2.sum;
    ls = max(n1.ls,n1.sum+n2.ls);
    rs = max(n2.rs,n2.sum+n1.rs);
    best = max(n1.best,max(n2.best,n1.rs+n2.ls));
    return Node(sum,ls,rs,best);
}

const int N = 50001;
int arr[N];
Node tree[N<<2];
int neg = -1000000000;


Node build(int node,int l,int r){
    if (l==r){
        return tree[node] = Node(arr[l],arr[l],arr[l],arr[l]);
    }
    int mid = (l+r) >> 1;
    return tree[node] = merge(build(node<<1,l,mid),build(node<<1|1,mid+1,r));
}

Node query(int node,int l,int r,int ll,int rr){
    if (l>rr || r<ll) return Node(neg,neg,neg,neg);
    if (l>=ll && r<=rr) return tree[node];
    int mid = (l+r) >> 1;
    return merge(query(node<<1,l,mid,ll,rr),query(node<<1|1,mid+1,r,ll,rr));
}


int main(){
#ifndef ONLINE_JUDGE
    readFile; writeFile; 
#endif
    fastIO;
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n);
    int q; cin>>q;
    while (q--){
        int a,b; cin>>a>>b;
        cout<<query(1,1,n,a,b).best<<"\n";
    }
}