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
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????\

pbd: 2017-03-04 04:43:32

Last edit: 2017-03-04 04:48:35
vladimira: 2017-02-25 14:24:01

Are there any succesful python submissions, cos mine give only TLEs ?

da_201501443: 2017-02-22 19:12:42

in java, I used segment tree and get TLE. How to make accurate my code?? Anybody please help me.
Thank you.


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