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
Davit Safrastyan: 2016-12-10 18:17:10

Find the solution of this problem in xoptutorials.com/spoj.php

Wumbolo: 2016-12-03 16:02:58

100th :Do GSS3 after this.

jawad_cs: 2016-11-18 08:42:40

taking size of array as 50000
and size of tree as 99999 (=2*50000-1)
gave me SEGSEV error

after increasing the sizes my solution got ac. Im curious to know why this thing happend. Can anyone please help me.

ryuga777: 2016-11-15 09:25:35

getting wrong answer on test case 9 .... tried almost everything... any help on corner case ??

kapoor_adhish: 2016-10-16 07:39:03

getting WA ....not TLE
using segtree....:(

i_dipu: 2016-10-07 12:35:30

used kadane algo for worst case scenario complexity is O(n*M), but TLE is the verdict !
how to improve this approach ? and also what is the limit of M ?

Last edit: 2016-10-07 13:23:13
Anirban Acharya: 2016-10-05 13:11:29

test cases are pretty weak.. I got 3 of my solutions passed by introducing several bugs :p .. so guys, even if your solution passes the test cases, make sure your algorithm and/or implementation is actually correct.

rahul: 2016-10-03 12:00:52

Source limit is 5kB?!
Weirdest thing ever

herkeyrefugee: 2016-10-02 06:51:19

Except for fast I/O don't look for anything , u can solve it .... :)

skroxx: 2016-09-29 21:22:34

without range of M how can we compute the complexity for this problem?


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 NODEJS PERL 6 VB.net