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
Stanislav Zholnin:
20150424 00:05:07
Limit on M is large enough to make O(mn) algorithm useless. Need O(n + m *log(n)) Last edit: 20150424 00:06:40 

bayram:
20150420 06:18:48
What's limit of M? 

zorkan:
20150402 23:47:01
I dont understand this question.


xxbloodysantaxx:
20150328 18:01:35
WOw man...


codedog:
20150202 11:00:42
if the number are 1 2 3 then should the max be 1 in the total array? 

Demjan:
20120810 17:22:39
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } means you are given numbers x and y, you have to find numbers i and j ( where x <= i <= j <= y ) such that sum a[i]+a[i+1]+...+a[j1]+a[j] is maximized 
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 