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
huangdachuan: 2021-08-21 23:37:58

See Finding subsegments with the maximal sum in the https://cp-algorithms.com/data_structures/segment_tree.html the key is to understand the recursive query logic.

matinzare: 2021-07-24 10:10:55

15007 × 50000 = 750350000 = > int
but after WA on 9 and change it to long long got AC :/

Waseem Ahmed: 2021-07-17 20:02:41

Finally solved it using Segment Trees.

Advice : While this is a standard problem and tutorials and codes are available online, solve it yourself for a wonderful learning experience on segment trees.

And thanks a lot to all the users who provided the sample test cases.

hello_baby: 2021-06-22 00:29:18

First solve the "maximum sum subarray" or "longest contiguous subarray sum" using divide and conquer, you can easily solve this.

ive1010: 2021-06-20 19:39:52

Small hint: need to store more than 1 information in Segment Tree

tropo_sphere: 2021-06-12 17:14:12

size of M?

loser_404: 2021-06-09 05:40:25

check this lecture from paska(cf-edu)
https://codeforces.com/edu/course/2/lesson/4/2

rimuru_404: 2021-06-05 11:39:18

Finally AC :-) . Good question...

csd_123: 2021-05-25 14:01:23

can it be solved using kadane's algorithm for each query

gupta_suraj143: 2021-05-14 14:53:25

can anyone provide me some extra test cases

Last edit: 2021-05-14 14:53:52

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