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
maddythakker:
20180610 11:49:42
FOR THE ONES GETTING TLE/WA ON JUDGE  9 :


shizukaa:
20180609 09:38:15
@thanos_tapras Thanks bro, reading comments helps ;) #was struck with the same problem 

a000:
20180523 23:38:29
savdhaan rahein, surakshit rahein, aur question sahi se padhein.


dipankar12:
20180510 16:17:38
Last edit: 20180510 16:18:02 

shubhank_7673:
20180509 18:45:48
getting WA on TC 9 using sqrt decomposition. can anybody help? 

chawla_harsh:
20180428 15:13:14
Can anyone help with case 9?


thanos_tapras:
20180426 13:23:35
getting WA in testcase no9. I use long long int and scanf/printf. Anybody help?


sanjeev:
20180405 12:34:56
this is the problem where you can spend time to learn the concepts. 

alysalhab5:
20180326 22:12:01
Testcase 9 gives TLE :( 

sktibrewal:
20180324 18:38:00
Use fast i/p. 
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 