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
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.

yeguzi2020: 2017-02-16 14:22:32

In C++, use cin with fast IO get TL, use scanf get AC. LOL

deepanshu_2015: 2017-02-12 10:12:32

getting wa after test case 9


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