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
shamiul93: 2017-04-21 00:23:26

Getting RTE in test case 9. :( Anybody help please.

anurag_333: 2017-04-08 14:42:13

10
-200 3 4 -200 6 2 4 -200 5 6
1
1 10
op should be 12

anurag_333: 2017-04-08 14:21:59

@ayush_1997 check test case of @marshmellow;
dont return 0 in querrys base case
return -15008//check least value of |ai|in ques

ayush_1997: 2017-04-01 07:48:57

wa on test case 9:(
tried everything..

rohit9934: 2017-03-30 15:35:11

Ohhhaaa This one is tough man,Specially for me who dont know how the f we can store 3,4 values simultaneously in a node.Took me 4-5 days understanding and solving.Can This problem be solved using BITs?

ace_of_spades: 2017-03-19 10:22:24

Last edit: 2017-03-19 21:38:09
marshmellow: 2017-03-19 09:55:24

input:
3
-1 -2 -3
1
1 3
output:
-1

scorpion_ajay: 2017-03-19 07:54:59

@anurag_333
No, i tried solving it using kadane but it gave me tle for obvious reasons that it can be O(n) in worst case !!
Also you have to check every time you query so it exceeds the time limit and ultimately you are better with seg_trees..

jeelapamy: 2017-03-13 18:05:59

hallelujah thank you god AC in one go

Last edit: 2017-03-13 18:06:13
anurag_333: 2017-03-08 19:39:08

can it be done by kadane's algorithm????\


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