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
rohit9934:
20170330 15:35:11
Ohhhaaa This one is tough man,Specially for me who dont know how the f we can store 3,4 values simultaneously in a node.Took me 45 days understanding and solving.Can This problem be solved using BITs? 

ace_of_spades:
20170319 10:22:24
Last edit: 20170319 21:38:09 

marshmellow:
20170319 09:55:24
input:


scorpion_ajay:
20170319 07:54:59
@anurag_333


jeelapamy:
20170313 18:05:59
hallelujah thank you god AC in one go Last edit: 20170313 18:06:13 

anurag_333:
20170308 19:39:08
can it be done by kadane's algorithm????\


pbd:
20170304 04:43:32
Last edit: 20170304 04:48:35 

vladimira:
20170225 14:24:01
Are there any succesful python submissions, cos mine give only TLEs ? 

da_201501443:
20170222 19:12:42
in java, I used segment tree and get TLE. How to make accurate my code?? Anybody please help me.


yeguzi2020:
20170216 14:22:32
In C++, use cin with fast IO get TL, use scanf get AC. LOL 
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 