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
Abhishek pratap singh:
20150618 13:26:20
@NITIKA Increase your tree array size. 

Deepak Singh Tomar:
20150616 23:14:22
segment_tree#1 

Liquid_Science:
20150615 10:28:12
Very stringent time limit for java programmers ,I guess that explains why around 15 java solution till now , Time limits should be seriously reconsidered to give other language programmers a chance 

Sajan mishra:
20150614 10:31:26
Last edit: 20150614 19:22:37 

silentcode:
20150613 20:54:07
@anando_du : ans should be 118 for this case no?? can you please explain how did you get 111?? Last edit: 20150613 20:55:32 

anando_du:
20150611 19:29:37
test case:


dastanforever:
20150608 10:49:52
WA on judge 9:( 

Praveen Kulkarni:
20150605 15:33:21
@NIKITA CHANDRA getting WA on judge 8 :(


Marko Puza:
20150522 17:55:47
I believe I most probably have the right algorithm; but I am not able to pass the time limit using Java.. Any ideas? 

faiz:
20150521 13:12:01
wow just solve this question amazing problem 
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 