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
siddharthp538:
20170704 06:19:44
Nice problem. Finally AC :) 

manasjoshi:
20170622 01:02:04
Very Weak test cases


babur:
20170620 09:44:27
This is what we call a classical question..!!:)


sudddddd:
20170617 13:31:30
Guys when submitting the code click "choose the file" not copy paste the code


nermatibhanu:
20170613 11:47:47
Are the given numbers sorted? 

mishra10:
20170610 05:27:34
Those of you getting W.A on test case 9 return negative number smaller than 15007 when there is no overlap..Hope this will help you to get AC. 

sharif ullah:
20170603 10:33:48
use scanf() printf() 

shabby005:
20170602 22:56:59
Getting TLE with whatsoever optimization in java. My solution has complexity of O(n+mlogn).


ista2000:
20170601 08:53:11
First segtree problem, first time AC, feeling confident <3 

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