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
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
eagleshadow: 2019-05-29 10:55:50

Try FREQUENT after this.
https://www.spoj.com/problems/FREQUENT/

dilip23: 2019-05-24 14:46:52

I am also getting TLE, but my solution is in c++.
Can anyone help me

johaer_wasif: 2019-05-23 18:42:51

If you are using int then it will overflow so use long long.

Last edit: 2019-05-23 18:43:26
hetp111: 2019-05-22 22:33:48

Braingasm..!


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