The problem is presented here as follows:

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. Given \$M\$ queries, your program must output the results of these queries.

Input

• The first line of the input file contains the integer \$N\$.
• In the second line, \$N\$ numbers follow.
• The third line contains the integer \$M\$.
• \$M\$ lines follow, where line \$i\$ contains 2 numbers \$x_i\$ and \$y_i\$.

Output

Your program should output the results of the \$M\$ queries, one query per line.

Example

Input:

3

-1 2 3

1 1 2

Output:

2

I'm solving the problem by using a segment tree - I am saving the sum, the max ,leftmost max, and the right most max at every node. I then search the graph to find the answer to a specific interval. How could I increase the speed of this code?

import java.util.Scanner;
//TLE
class GSS1 {


static class Node{
    int max;
    int MaxL;
    int MaxR;
    int sum;
    
    public Node(int max, int MaxL, int MaxR, int sum){
        this.max=max;
        this.MaxL=MaxL;
        this.MaxR=MaxR;
        this.sum=sum;
    }
    
    public Node(){
        
    }
}

static class SegmentTree{
    
    private Node[] tree;
    private int maxsize;
    private int height;
 
    private  final int STARTINDEX = 0; 
    private  final int ENDINDEX;
    private  final int ROOT = 0;
    Node s;
 
    public SegmentTree(int size){
        height = (int)(Math.ceil(Math.log(size) /  Math.log(2)));
        maxsize = 2 * (int) Math.pow(2, height) - 1;
        tree = new Node[maxsize];
        for(int i=0;i<tree.length;i++){
            tree[i]=new Node();
        }
        ENDINDEX = size - 1; 
        s=new Node();
        s.MaxL=Integer.MIN_VALUE;
        s.MaxR=Integer.MIN_VALUE;
        s.sum=Integer.MIN_VALUE;
        s.max=Integer.MIN_VALUE;
        
    }
    
    
    
    
    private int leftchild(int pos){
        return 2 * pos + 1;
    }
 
    private int rightchild(int pos){
        return 2 * pos + 2;
    }
 
    private int mid(int start, int end){
        return (start + (end - start) / 2); 
    }
    
    private Node constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current){
        if (startIndex == endIndex)
        {
            tree[current].max=tree[current].MaxL=tree[current].MaxR=tree[current].sum=elements[startIndex];    
            return tree[current];
        }
        int mid = mid(startIndex, endIndex);
        Node left=constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current));
        Node right=constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current));
        tree[current].max = Math.max(left.max, right.max);
        tree[current].MaxL = Math.max(left.MaxL , left.sum+right.MaxL);
        tree[current].MaxR = Math.max(right.MaxR , right.sum+left.MaxR);
        tree[current].sum = left.sum+right.sum;
        return tree[current];
    }
 
    public void constructSegmentTree(int[] elements){
        constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT);    
    }
 
    private Node getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current){
        
        if (queryStart <= startIndex && queryEnd >= endIndex ){
            return tree[current];
        }
        if (endIndex < queryStart || startIndex > queryEnd){
            return s;
        }
        int mid = mid(startIndex, endIndex);
        
        Node left=getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current));
        Node right=getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));
        
        Node current_Node=new Node();
        current_Node.max = Math.max(left.max, right.max);
        current_Node.MaxL = Math.max(left.MaxL , left.sum+right.MaxL);
        current_Node.MaxR = Math.max(right.MaxR , right.sum+left.MaxR);
        current_Node.sum = left.sum+right.sum;
        return current_Node;
        
        
    }
 
    public int getMaxSum(int queryStart, int queryEnd){
        if(queryStart < 0 || queryEnd > tree.length)
        {System.out.println("inside negative");
            return Integer.MIN_VALUE;
        }
        return getMax(getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT));
    }
    
    public int getMax(Node r){
        return Math.max(Math.max(r.max, r.MaxL),Math.max(r.MaxR, r.sum));
    }
    
    public int getFirst(){
        return tree[0].MaxL;
    }
    
}


public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    
    int numbers[]=new int [input.nextInt()];
    
    for(int i=0;i<numbers.length;i++){
        numbers[i]=input.nextInt();
    }
    
    SegmentTree tree=new SegmentTree(numbers.length);
    tree.constructSegmentTree(numbers);
    
    int cases=input.nextInt();
    
    int x;
    int y;
    int query;
    for(int i=0;i<cases;i++){
        x=input.nextInt()-1;
        y=input.nextInt()-1;
        
        System.out.println(tree.getMaxSum(x, y));
    }
}
}