SPOJ.com - Problem GSS1

GSS1 - Can you answer these queries I

#tree

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

Submit solution!

hide comments

< Previous 6 7 8 9 10 11 12 13 14 15 16 Next >

	s_h_i_1: 2019-07-27 09:28:23 use segment tree .
	scolar_fuad: 2019-07-12 05:37:14 I am getting WA on 9th test case and why is there anyone like me ?
	landofkings: 2019-07-01 01:27:54 if getting wa, try to find bug in query. for extreme cases it must be like . if(low > high){ Tree ziz ; ziz.tsum = 0 ; ziz.psum = minn; ziz.ssum = minn ; ziz.maxsum = minn ; return ziz ; } if(st > high or endd < low ){ Tree ziz ; ziz.tsum = 0 ; ziz.psum = minn ; ziz.ssum = minn ; ziz.maxsum = minn; return ziz ; }
	sagarrawat: 2019-06-28 19:09:56 finally, AC (Segment tree + fast i/o in java) Last edit: 2019-06-28 19:10:32
	inderjeet_333: 2019-06-18 09:56:02 @Kesh getting wa on 9th test case . but my program does compute your example test case correctly. Last edit: 2019-06-18 10:08:10
	kanishk779: 2019-06-13 13:15:49 @somanshu_s what is the meaning of prefix sum and suffix sum and total sum in this problem.
	pan1640616850: 2019-06-05 05:29:38 if you use long long,you will AC!
	chypsd: 2019-06-03 09:47:48 GOT TLE AFTER TEST CASE 9
	kesh4281: 2019-05-31 09:48:29 for WA on 9th-- check for 4 -2 1 1 -2 1 1 4 ans shud be 2. TRY SPOJ TOOLKIT I/P no. 25
	nodir: 2019-05-29 14:42:55 How can I understand on which test case my code gets "WA"? Last edit: 2019-05-29 14:54:42

Submit solution!

Added by:	Nguyen Dinh Tu
Date:	2006-11-01
Time limit:	1s
Source limit:	5000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO NODEJS PERL6 VB.NET