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

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

hide comments
2016-01-11 15:40:08
Getting WA with judge 9
2015-12-25 07:35:45
no empty subset
2015-12-25 07:35:01
quite tricky...
2015-12-23 17:04:08 anshal dwivedi
uff! after 3 hours debugging finally got AC........ :)
2015-12-16 18:28:11 MAYANK NARULA
To think the problem designer could have come this far in thinking ahead !!!.....Finally solved it...
2015-12-08 21:56:50 m.ajaj94
This problem really taught me a lot
though one simple mistake caused me to submit 12 WAs :/
2015-11-29 06:51:37
If the aeeay is 1-inexed how is the output of the sample 2 ?
2015-11-26 09:04:06
Learnt a load of new things
2015-11-15 20:33:35
Can't this be solved using maximum subarray algorithm from CLRS?
2015-10-21 02:14:27
The time limit is per test case and it is very tight, so you don't want to use an buffered output otherwise you'll get a TLE.

Last edit: 2015-10-25 22:14:08
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.