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
alysalhab5:
20180326 22:12:01
Testcase 9 gives TLE :( 

sktibrewal:
20180324 18:38:00
Use fast i/p. 

siddsoj_5444:
20180322 16:29:58
used SEG trees ... still wrong answer on TC 9 anyone got passed ... please help


siddsoj_5444:
20180322 16:23:36
@ista2000 what do you return in case of no overlap? tag me please 

riddhyasona:
20180321 18:06:59
zenosama is awesome. Last edit: 20180403 10:45:48 

vaifai:
20180309 13:57:55
TL is very strict for JAVA. 

nadstratosfer:
20180225 06:42:01
pykay, probably blanklines somewhere in the input. You're wasting your time anyway, problems from this series have TL too tight for Python solution to pass. 

pykay:
20180223 19:22:45
test case 9 run time error(python 3.5). any suggestions? 

chaitya62:
20180221 16:51:50
I don't understand why I am getting a TLE, I am using scanf, printf, using bit manipulation for multiplication and division. 

satyampnc:
20180201 20:55:19
use long long int :)

Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 