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
Deepak Singh Tomar: 2015-06-16 23:14:22

segment_tree#1

Liquid_Science: 2015-06-15 10:28:12

Very stringent time limit for java programmers ,I guess that explains why around 15 java solution till now , Time limits should be seriously reconsidered to give other language programmers a chance

Sajan mishra: 2015-06-14 10:31:26

Last edit: 2015-06-14 19:22:37
silentcode: 2015-06-13 20:54:07

@anando_du : ans should be 118 for this case no?? can you please explain how did you get 111??

Last edit: 2015-06-13 20:55:32
anando_du: 2015-06-11 19:29:37

test case:
5
3 -10 100 -2 20
1
1 5
output:
118

Last edit: 2015-07-08 08:28:54
dastanforever: 2015-06-08 10:49:52

WA on judge 9:(

Praveen Kulkarni: 2015-06-05 15:33:21

@NIKITA CHANDRA getting WA on judge 8 :(

Marko Puza: 2015-05-22 17:55:47

I believe I most probably have the right algorithm; but I am not able to pass the time limit using Java.. Any ideas?

faiz: 2015-05-21 13:12:01

wow just solve this question amazing problem

LazarusLong: 2015-05-13 16:44:32

For people with a case-sensitive brain (like me), the problem statement should be:

"You are given a sequence a[1], a[2], ..., a[N] . ( |a[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ).".


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