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 23 24 25 26 27 28 29 30 31 32 33 Next >

	Sarthak Munshi: 2015-10-08 17:34:55 Be careful! You don't have to find the max element in the range . You have to find maximum subvector sum in the range . i . e if array is {1,2,-4,1}......answer should be 3 because 1+2>than all combinations added together linearly .
	Aayush: 2015-10-02 19:36:38 I am suffering in judge 9. Getting WA. I am using ST concept and I am confident with my logic. Please someone help me. Give me some really tough test cases. Thank you Edit:: Finally done.. Was missing a case.. 10 WA cause of that stupid case:( Last edit: 2015-10-02 19:49:50
	Oasis: 2015-09-28 18:16:14 Very Good Question! My second segment tree problem :D
	dev: 2015-09-16 09:11:40 Finally Ac after too many wa and sigsev ...had to comment ! worth trying...learnt a lot...used seg tree !! :)
	kamjpvv4m7: 2015-09-12 09:52:11 Time is limited so never use "cin" and "cout"
	elise: 2015-09-08 02:13:16 No need to use lazy propagation, no need to use long long int. Great problem.
	theweblover007: 2015-09-07 18:40:16 Is lazy propog. required to solve this ?
	Pratik S: 2015-08-27 19:23:29 M in long long int(C++)? guys W.A in judge 9 ive seen several ppl say the same any1 who could solve this problem plzz help
	PKJ: 2015-08-22 13:08:15 Note that the answer to a query could even be negative.
	hnvahidi: 2015-08-12 01:35:48 i don't get it :\| why such a tight time limit ? it will garbage all the theory behind problem due to such a constant decrease of time

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