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
inderjeet_333:
20190618 09:56:02
@Kesh getting wa on 9th test case .


nitin_uniyal21:
20190617 09:47:45
No luck with python. https://ideone.com/2rpKXD


kanishk779:
20190613 13:15:49
@somanshu_s what is the meaning of prefix sum and suffix sum and total sum in this problem. 

pan1640616850:
20190605 05:29:38
if you use long long,you will AC! 

chypsd:
20190603 09:47:48
GOT TLE


kesh4281:
20190531 09:48:29
for WA on 9th


nodir:
20190529 14:42:55
How can I understand on which test case my code gets "WA"? Last edit: 20190529 14:54:42 

eagleshadow:
20190529 10:55:50
Try FREQUENT after this.


dilip23:
20190524 14:46:52
I am also getting TLE, but my solution is in c++.


johaer_wasif:
20190523 18:42:51
If you are using int then it will overflow so use long long. Last edit: 20190523 18:43:26 
Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 