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
satyampnc:
20180201 20:55:19
use long long int :)


sherlock11:
20180131 07:23:46
use scanf and printf for AC........


akashgupta13:
20180128 17:44:13
no constraints for queries? 

viniet_sw:
20180126 12:50:52
badia question hai madarjaat 

eicaptain:
20180126 02:01:51
This problem can also be solved by dsu with complexity O(n alpha(n)) 

coolio_1:
20180118 20:21:00
Assume 1 based indexing for the input array as well as the queries. So the input array will be from [1...n]. Cost me a couple of WA! :( 

oclewx:
20180117 18:37:39
first time i got runtime error (SIGSEGV) , then TLE then WA and finally AC


manvscode:
20180107 15:15:58
@geek_lady take i=1 and j=1 (assuming 0indexing in array) we get sum =2.


excursionist:
20180102 18:21:34
Testcase 9 gives TLE :( 

senacoder111:
20180102 16:17:58
must if you want to learn segment tree 
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 