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
hacoder: 2019-08-16 22:31:50

For this input:
7
5 -1 7 6 1 9 3
1
1 7

Why is the output 30, shouldn't it be 31?

rocky_12: 2019-08-14 09:16:03

I am stuck at test case 9 tle used segment tree with fast input output

urjajn123: 2019-08-12 18:09:10

TLE using segment tree

urjajn123: 2019-08-12 18:08:36

TLE using segment tree

rahulsinghk: 2019-08-10 06:43:28

TLE no matter what!!

hacoder: 2019-08-09 13:26:22

I don't understand what Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } means?

selfcoder24: 2019-08-08 11:30:16

Do not return 0 in case of base case. Return -15008. Stupid case costed 6 WA.

leductoan: 2019-08-08 06:15:26

AC in one go

const_variable: 2019-08-03 13:53:34

I'm getting TLE even after using basic segment tree function. What part can I improve on?

s_h_i_1: 2019-07-27 09:28:23

use segment tree .


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