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
dinkar:
20170528 11:03:44
finally After 8 TLEs 

sfialok98:
20170527 21:34:14
Good One on Segment trees..


Joyjit Choudhury:
20170525 05:03:27
After fixing all probable bugs in my code, I was still getting TLE on Test Case 9.


swas99:
20170520 08:13:45
Failed to do it in java. Wasted my time even trying to optimize the input scan. Just reading the input using Scanner or Buffered reader give TLE. Due to source code limit, I could not try other options.


shamiul93:
20170421 00:23:26
Getting RTE in test case 9. :( Anybody help please. 

anurag_333:
20170408 14:42:13
10


anurag_333:
20170408 14:21:59
@ayush_1997 check test case of @marshmellow;


ayush_1997:
20170401 07:48:57
wa on test case 9:(


rohit9934:
20170330 15:35:11
Last edit: 20180122 07:52:37 

ace_of_spades:
20170319 10:22:24
Last edit: 20170319 21:38:09 
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 