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
pratyushgadge1: 2023-11-02 20:48:21

WA on case 9????

vishalrawat_1: 2023-08-28 09:31:14

need a sherlock brain for the testcase where my code get failed

vikas_102: 2023-06-12 15:24:39

i learnt a lot form this question.this question was equal to 5 seg t questions.

iskhakkutbilim: 2023-03-02 15:25:40

is it can be solved by segment tree(maximum subarray sum)

xarma: 2023-01-26 08:12:16

You should avoid printing answer for empty subarray (i.e 0) , They are asking for a subbarray with atleast one element

Last edit: 2023-01-26 08:12:35
yszokk: 2022-11-11 14:01:50

OMG.Quite Difficult:(

rotcar07: 2022-09-22 09:25:59

Why wrong answer on test #9? Did I missed something?

ma_niu_bi: 2022-08-30 14:06:37

Why?

ma_niu_bi: 2022-08-30 13:38:07

wrong answer on test #9? help!

Phi: 2022-08-15 14:01:47

I'm not sure I understand the query definition? Are we looking for a sum of a[i] up to a[j]? If yes, why do we need max{} then (it would be a max from a single value)? Or are we interested in a max over a[i] up to a[j]? If yes, why are there pluses between a[i]s?

Last edit: 2022-08-15 14:01:59

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