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
flyingduchman_:
20160721 14:16:15
Took almost one month to get accepted 

naksh9619:
20160719 02:00:07
good problem :) Last edit: 20160719 22:32:40 

baadshah_:
20160626 14:15:48
Finally AC took whole DAY!! 

Deepak :
20160618 17:27:55
finally AC..great problem for beginners.thanks @AbhishekRajput 

oalieno:
20160511 15:43:27
Did anyone use Treap to solve this problem?


mars_ch:
20160502 08:34:46
同意楼上！！ 

yousiki:
20160501 05:38:06
TL is too strict 

geekyadity:
20160414 15:04:18
Use printf, scanf. ( sync_with_stdio(false) ) gives TLE with the same code 

a_b_c12345:
20160410 09:16:53
yoo..!! after 2 WA and 2 TLE finally accepted. To get AC from TLE just changed input array and tree into global. 

minhthai:
20160214 14:50:58
why hate java so much :((

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 