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
sanket407:
20160205 14:27:47
FOR JAVA GUYS :


nib:
20160125 10:38:20
Extremely strict TL. Same idea using struct passed, but using vector gets TLE :/ 

proficient:
20160118 17:09:32
The problem requires fast input/output, I had a TLE even with sync_with_stdio(false) and tie(0) 

sanyal18:
20160111 15:40:08
Getting WA with judge 9 

nyxf4ll_:
20151225 07:35:45
no empty subset 

nyxf4ll_:
20151225 07:35:01
quite tricky... 

anshal dwivedi:
20151223 17:04:08
uff! after 3 hours debugging finally got AC........ :)


MAYANK NARULA:
20151216 18:28:11
To think the problem designer could have come this far in thinking ahead !!!.....Finally solved it... 

m.ajaj94:
20151208 21:56:50
This problem really taught me a lot


justforpractic:
20151129 06:51:37
If the aeeay is 1inexed how is the output of the sample 2 ? 
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 