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
leafbebop:
20170601 08:33:16
SQ Table make it possible to have a <O(n log n), O(1)> approach. Cheers for O(1). 

mkfeuhrer:
20170530 19:38:16
segment tree must!!....tle so use scanf/printf .. 

ajeyo:
20170529 14:54:02
After so mant TLEs just used fast I/O and AC 

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;

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 