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
kapoor_adhish:
20161016 07:39:03
getting WA ....not TLE


i_dipu:
20161007 12:35:30
used kadane algo for worst case scenario complexity is O(n*M), but TLE is the verdict !


Anirban Acharya:
20161005 13:11:29
test cases are pretty weak.. I got 3 of my solutions passed by introducing several bugs :p .. so guys, even if your solution passes the test cases, make sure your algorithm and/or implementation is actually correct. 

rahul:
20161003 12:00:52
Source limit is 5kB?!


herkeyrefugee:
20161002 06:51:19
Except for fast I/O don't look for anything , u can solve it .... :) 

skroxx:
20160929 21:22:34
without range of M how can we compute the complexity for this problem?


srinath:
20160920 10:11:46
Took me 13 submissions to get AC ;) 

Eduard Rostomyan:
20160919 16:16:57
Will the BIT work here? 

stiffler22:
20160906 23:47:00
using maximum sub array and getting WA on judge 9. Which case am I getting wrong? 

rampant_lancer:
20160906 18:23:35
getting sigsegv can someone point out some common mistakes.I am using segment tree. Last edit: 20160906 18:23:56 
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 JS NODEJS PERL 6 VB.net 