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
theweblover007:
20150907 18:40:16
Is lazy propog. required to solve this ? 

Pratik S:
20150827 19:23:29
M in long long int(C++)?


PKJ:
20150822 13:08:15
Note that the answer to a query could even be negative. 

reverser:
20150812 23:47:29
Last edit: 20150813 00:11:59 

hnvahidi:
20150812 01:35:48
i don't get it :


lavish goel:
20150731 12:34:26
Why I am getting TLE? :(


kejriwal:
20150729 00:36:12
Nice one :) learnt something :D 

Abhinav:
20150727 12:36:09
@Utkarsh Gupta


Rahul Jain:
20150721 18:44:24
Amazingly nice question. Learnt a lot of things on how exactly to use segment trees for Range queries. 

shravinson:
20150719 20:49:48
why am i getting WA

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 