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
mkfeuhrer: 2017-05-30 19:38:16

segment tree must!!....tle so use scanf/printf ..

ajeyo: 2017-05-29 14:54:02

After so mant TLEs just used fast I/O and AC

dinkar: 2017-05-28 11:03:44

finally After 8 TLEs

sfialok98: 2017-05-27 21:34:14

Good One on Segment trees..
Use fast I/O only...
Costed me TLE...
and Learned a lot..!!

Joyjit Choudhury: 2017-05-25 05:03:27

After fixing all probable bugs in my code, I was still getting TLE on Test Case 9.
Changed cin, cout to printf, scanf and removed ios::sync_with_stdio(false) and AC :)

swas99: 2017-05-20 08:13:45

Failed to do it in java. Wasted my time even trying to optimize the input scan. Just reading the input using Scanner or Buffered reader give TLE. Due to source code limit, I could not try other options.
Please let me know if anyone got AC using java

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


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