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
gulshan_raj:
20151126 09:04:06
Learnt a load of new things 

irbis9:
20151115 20:33:35
Can't this be solved using maximum subarray algorithm from CLRS? 

carofe82:
20151021 02:14:27
The time limit is per test case and it is very tight, so you don't want to use an buffered output otherwise you'll get a TLE. Last edit: 20151025 22:14:08 

Parikshit:
20151019 17:08:21
stupendous problem!! 

Sarthak Munshi:
20151008 17:34:55
Be careful! You don't have to find the max element in the range . You have to find maximum subvector sum in the range . i . e if array is {1,2,4,1}......answer should be 3 because 1+2>than all combinations added together linearly . 

Aayush:
20151002 19:36:38
I am suffering in judge 9. Getting WA. I am using ST concept and I am confident with my logic.


Oasis:
20150928 18:16:14
Very Good Question! My second segment tree problem :D 

dev:
20150916 09:11:40
Finally Ac after too many wa and sigsev ...had to comment ! worth trying...learnt a lot...used seg tree !! :) 

kamjpvv4m7:
20150912 09:52:11
Time is limited so never use "cin" and "cout" 

elise:
20150908 02:13:16
No need to use lazy propagation, no need to use long long int.

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 