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
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
Ohhhaaa This one is tough man,Specially for me who dont know how the f we can store 3,4 values simultaneously in a node.Took me 45 days understanding and solving.Can This problem be solved using BITs? 

ace_of_spades:
20170319 10:22:24
Last edit: 20170319 21:38:09 

marshmellow:
20170319 09:55:24
input:


scorpion_ajay:
20170319 07:54:59
@anurag_333

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 