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
Tomasz Plaskota: 2016-02-12 13:51:16

as mentioned before: make sure you use fast input output cause there is ALOT of that.
Also to earlier questions: maximum of subarray algorithm works in general but you will still find it too slow for amount of queries M that test cases provide (even fastest MSA is O(N*M), while ST will be O(N*1))

sanket407: 2016-02-05 14:27:47

FOR JAVA GUYS :
USE fast input reader for ip
USe stringbiulder to store op and print all at once at the end
And maybe some optimizations inside

nib: 2016-01-25 10:38:20

Extremely strict TL. Same idea using struct passed, but using vector gets TLE :/

proficient: 2016-01-18 17:09:32

The problem requires fast input/output, I had a TLE even with sync_with_stdio(false) and tie(0)

sanyal18: 2016-01-11 15:40:08

Getting WA with judge 9

nyxf4ll_: 2015-12-25 07:35:45

no empty subset

nyxf4ll_: 2015-12-25 07:35:01

quite tricky...

anshal dwivedi: 2015-12-23 17:04:08

uff! after 3 hours debugging finally got AC........ :)

MAYANK NARULA: 2015-12-16 18:28:11

To think the problem designer could have come this far in thinking ahead !!!.....Finally solved it...

m.ajaj94: 2015-12-08 21:56:50

This problem really taught me a lot
though one simple mistake caused me to submit 12 WAs :/


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