GSS1  Can you answer these queries I
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 xi and yi.
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
hide comments
somanshu_s:
20171209 22:12:53
Hint for this problem : Build segment tree on this structure :


chachaji_harsh:
20171208 08:00:03
Last edit: 20171208 14:14:56 

bash_turtle:
20171204 18:05:00
i am getting a runtine error (SIGSEGV ).Can someone help please


manuparmar35:
20171129 16:38:04
really a difficult problem someone please explain how can it be solved 

geek_lady:
20171115 21:34:41
i donot get given testcase .


sanjolly1997:
20171114 17:37:04
can someone help in testcase 9 it is showing TLE i have also used scanf and printf instead of cin & cout. 

ramini1996:
20171106 20:10:01
Took a day to solve it. Not an easy one. My first in Segment Trees. 

kuuji:
20171030 05:28:52
forgot to put "\n" ._. hahah 

anubhav25:
20171009 08:35:26
Finally did it ::)


striver_79:
20171005 22:46:24
my first in segment tree! 
Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  0.115s0.230s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 