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
justforpractic: 2015-11-29 06:51:37

If the aeeay is 1-inexed how is the output of the sample 2 ?

gulshan_raj: 2015-11-26 09:04:06

Learnt a load of new things

irbis9: 2015-11-15 20:33:35

Can't this be solved using maximum subarray algorithm from CLRS?

carofe82: 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
Parikshit: 2015-10-19 17:08:21

stupendous problem!!

Sarthak Munshi: 2015-10-08 17:34:55

Be careful! You don't have to find the max element in the range . You have to find maximum subvector sum in the range . i . e if array is {1,2,-4,1}......answer should be 3 because 1+2>than all combinations added together linearly .

Aayush: 2015-10-02 19:36:38

I am suffering in judge 9. Getting WA. I am using ST concept and I am confident with my logic.
Please someone help me. Give me some really tough test cases.
Thank you

Edit:: Finally done.. Was missing a case.. 10 WA cause of that stupid case:(

Last edit: 2015-10-02 19:49:50
Oasis: 2015-09-28 18:16:14

Very Good Question! My second segment tree problem :D

dev: 2015-09-16 09:11:40

Finally Ac after too many wa and sigsev ...had to comment ! worth trying...learnt a lot...used seg tree !! :)

kamjpvv4m7: 2015-09-12 09:52:11

Time is limited so never use "cin" and "cout"


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